Problem Description

You need to identify invalid transactions from a list of transaction records. A transaction is considered possibly invalid if it meets either of these conditions:

1. The transaction amount exceeds $1000
2. The transaction occurs within 60 minutes (inclusive) of another transaction with the same person's name but in a different city

Each transaction is given as a string with comma-separated values in the format: "name,time,amount,city" where:

• name is the person's name
• time is when the transaction occurred (in minutes)
• amount is the transaction amount in dollars
• city is where the transaction took place

For example, if "Alice" makes a transaction in "NYC" at time 10, and another transaction in "LA" at time 50, both transactions are invalid because they occur within 60 minutes of each other (50 - 10 = 40 minutes ≤ 60) and are in different cities.

Your task is to return a list of all transactions that are possibly invalid. The transactions can be returned in any order.

The solution uses a hash table to group transactions by name and checks each transaction against both validity conditions. It maintains a set of indices to track which transactions are invalid, avoiding duplicates. For the time-based condition, it compares each transaction with all other transactions of the same name, marking both as invalid if they occur in different cities within 60 minutes of each other.

Intuition

The key insight is that we need to check two independent conditions for each transaction, and a transaction can be invalid for either reason (or both).

For the first condition (amount > $1000), it's straightforward - we just need to check each transaction's amount individually.

For the second condition, we need to compare transactions that share the same name. This suggests grouping transactions by name would be efficient. Once grouped, we can compare each transaction within a group to find those that occur in different cities within 60 minutes of each other.

The tricky part is that when two transactions violate the time/city rule, both transactions become invalid, not just one. For example, if Alice has transactions in NYC at time 10 and LA at time 50, both transactions are marked invalid, not just the later one.

To handle this efficiently, we can:

1. Group all transactions by the person's name using a hash table
2. For each transaction, check if it violates the amount rule
3. For each transaction, compare it with all other transactions under the same name to check the time/city rule
4. Use a set to track invalid transaction indices to avoid duplicates (since a transaction might be invalid for multiple reasons or match with multiple other transactions)

The time complexity is acceptable because we only compare transactions within the same name group, not across all transactions. This grouping strategy significantly reduces the number of comparisons needed.

Learn more about Sorting patterns.

Solution Approach

We use a hash table combined with simulation to solve this problem. Here's the step-by-step implementation:

1. Data Structures Setup:

• Create a hash table d using defaultdict(list) where each key is a person's name and the value is a list of their transactions
• Create a set idx to store indices of invalid transactions (using a set prevents duplicates)

2. Parse and Store Transactions: For each transaction at index i:

• Parse the transaction string by splitting on commas: name, time, amount, city = x.split(",")
• Convert time and amount to integers
• Store the transaction in the hash table as a tuple: d[name].append((time, city, i))
  • We store (time, city, index) for each transaction under the person's name

3. Check Invalid Conditions:

For each transaction, we check both invalidity conditions:

Condition 1 - Amount Check:

• If amount > 1000, add index i to the idx set

Condition 2 - Time/City Check:

• Iterate through all transactions with the same name: for t, c, j in d[name]
• For each pair, check if:
  • Cities are different: c != city
  • Time difference is within 60 minutes: abs(time - t) <= 60
• If both conditions are met, mark both transactions as invalid:
  • Add current transaction index i to idx
  • Add the compared transaction index j to idx

4. Build Result:

• After processing all transactions, convert the set of invalid indices to actual transaction strings
• Return [transactions[i] for i in idx] to get all invalid transactions

The algorithm efficiently groups related transactions together and only compares transactions within the same name group, avoiding unnecessary comparisons across different names. The use of a set for tracking invalid indices ensures no duplicates in the final result.

Example Walkthrough

Let's walk through a small example with these transactions:

transactions = ["alice,20,800,mtv", "alice,50,100,beijing", "alice,51,100,mtv", "bob,55,1200,mtv"]

Step 1: Parse and Group Transactions

We create a hash table d to group by name and a set idx for invalid indices:

• Parse transaction 0: "alice,20,800,mtv" → name="alice", time=20, amount=800, city="mtv"
  • Add to d["alice"] = [(20, "mtv", 0)]
• Parse transaction 1: "alice,50,100,beijing" → name="alice", time=50, amount=100, city="beijing"
  • Add to d["alice"] = [(20, "mtv", 0), (50, "beijing", 1)]
• Parse transaction 2: "alice,51,100,mtv" → name="alice", time=51, amount=100, city="mtv"
  • Add to d["alice"] = [(20, "mtv", 0), (50, "beijing", 1), (51, "mtv", 2)]
• Parse transaction 3: "bob,55,1200,mtv" → name="bob", time=55, amount=1200, city="mtv"
  • Add to d["bob"] = [(55, "mtv", 3)]

Step 2: Check Each Transaction for Invalidity

Transaction 0 ("alice,20,800,mtv"):

• Amount check: 800 ≤ 1000 ✓ (valid)
• Time/city check with other alice transactions:
  • Compare with (50, "beijing", 1): |20-50| = 30 ≤ 60 and "mtv" ≠ "beijing" → Both 0 and 1 are invalid!
  • Compare with (51, "mtv", 2): |20-51| = 31 ≤ 60 but "mtv" = "mtv" ✓ (same city, ok)
• Add indices 0 and 1 to idx = {0, 1}

Transaction 1 ("alice,50,100,beijing"):

• Amount check: 100 ≤ 1000 ✓ (valid)
• Time/city check with other alice transactions:
  • Compare with (20, "mtv", 0): |50-20| = 30 ≤ 60 and "beijing" ≠ "mtv" → Both 1 and 0 are invalid!
  • Compare with (51, "mtv", 2): |50-51| = 1 ≤ 60 and "beijing" ≠ "mtv" → Both 1 and 2 are invalid!
• Add indices 0, 1, 2 to idx = {0, 1, 2} (0 and 1 already there)

Transaction 2 ("alice,51,100,mtv"):

• Amount check: 100 ≤ 1000 ✓ (valid)
• Time/city check with other alice transactions:
  • Compare with (20, "mtv", 0): |51-20| = 31 ≤ 60 but "mtv" = "mtv" ✓ (same city, ok)
  • Compare with (50, "beijing", 1): |51-50| = 1 ≤ 60 and "mtv" ≠ "beijing" → Both 2 and 1 are invalid!
• Add indices 1, 2 to idx = {0, 1, 2} (already there)

Transaction 3 ("bob,55,1200,mtv"):

• Amount check: 1200 > 1000 → Invalid!
• Time/city check: Bob has no other transactions to compare
• Add index 3 to idx = {0, 1, 2, 3}

Step 3: Build Result

Invalid indices: {0, 1, 2, 3}

Return all four transactions:

["alice,20,800,mtv", "alice,50,100,beijing", "alice,51,100,mtv", "bob,55,1200,mtv"]

Note how alice's transactions at indices 0, 1, and 2 are all invalid due to the time/city rule (even though none exceed $1000), while bob's transaction is invalid due to exceeding$1000.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The code iterates through each transaction once in the outer loop, which takes O(n) time. For each transaction with name name, it checks all previously processed transactions with the same name in the inner loop (for t, c, j in d[name]). In the worst case, all n transactions could have the same name, meaning for the i-th transaction, we check against i-1 previous transactions. This results in 1 + 2 + 3 + ... + (n-1) = n(n-1)/2 comparisons, which is O(n²).

Space Complexity: O(n)

The space complexity consists of:

• Dictionary d: stores at most n transaction records (one entry per transaction), each containing (time, city, index) tuples, requiring O(n) space
• Set idx: stores at most n indices (in the worst case, all transactions are invalid), requiring O(n) space
• The output list: stores at most n transactions, requiring O(n) space

Therefore, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Missing Bidirectional Marking for Time-Based Invalid Transactions

A critical mistake is forgetting to mark both transactions as invalid when they violate the time/city condition. Many developers incorrectly mark only the current transaction being processed, missing the fact that if transaction A makes transaction B invalid, then B also makes A invalid.

Incorrect Implementation:

# WRONG: Only marks current transaction as invalid
for prev_time, prev_city, prev_index in transactions_by_name[name]:
    if prev_city != city and abs(time - prev_time) <= 60:
        invalid_indices.add(index)  # Only adds current index
        # Missing: invalid_indices.add(prev_index)

Why This Fails: Consider these transactions:

• "Alice,10,50,NYC"
• "Alice,40,100,LA"

If we only mark the second transaction when comparing it with the first, we miss that the first transaction is also invalid due to the second one.

Correct Implementation:

# CORRECT: Marks both transactions as invalid
for prev_time, prev_city, prev_index in transactions_by_name[name]:
    if prev_city != city and abs(time - prev_time) <= 60:
        invalid_indices.add(index)      # Add current transaction
        invalid_indices.add(prev_index)  # Add compared transaction

Additional Pitfall: Duplicate Comparisons Without Set

Another common mistake is using a list instead of a set for invalid_indices, which can lead to duplicate entries in the result:

Incorrect:

invalid_indices = []  # Using list allows duplicates
# Later...
invalid_indices.append(index)  # Can add same index multiple times

Correct:

invalid_indices = set()  # Set automatically handles duplicates
invalid_indices.add(index)  # Won't create duplicates

The set ensures each invalid transaction appears only once in the final result, even if it's marked invalid multiple times due to different conditions or multiple conflicting transactions.