1169. Invalid Transactions - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Invalid Transactions is a problem about detecting potentially fraudulent transaction records. You are given a list of transactions, where each transaction is represented as a string in the format "{name},{time},{amount},{city}". A transaction is considered invalid if either of the following conditions is true:

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

If a transaction meets either condition, it is possibly invalid and should be flagged. The task is to return all such invalid transactions from the list. If none are invalid, return an empty list. Order of output does not matter.

Constraints:

1 <= transactions.length <= 1000 (up to 1000 transactions).
Each transaction string is formatted as described (name,time,amount,city).
name and city consist of lowercase English letters, length 1 to 10.
time is an integer between 0 and 1000 (minutes).
amount is an integer between 0 and 2000.

These constraints ensure that a brute-force solution (checking every pair of transactions) is feasible in the worst case (1000 transactions results in at most ~1,000,000 comparisons). However, we will also explore more efficient strategies.

Example 1:

Input: ["alice,20,800,mtv", "alice,50,100,beijing"]  
Output: ["alice,20,800,mtv", "alice,50,100,beijing"]

Both transactions are invalid. The first is invalid because there is another transaction for "alice" within 60 minutes (20 to 50 minutes) in a different city (mtv vs. beijing), and the second is invalid for the same reason.

Example 2:

Input: ["alice,20,800,mtv", "alice,50,1200,mtv"]  
Output: ["alice,50,1200,mtv"]

The second transaction is invalid since its amount 1200 exceeds $1000. The first transaction is not invalid – although it’s within 30 minutes of another "alice" transaction, that other transaction is in the same city (both in "mtv"), so the city condition isn't met.

Example 3:

Input: ["alice,20,800,mtv", "bob,50,1200,mtv"]  
Output: ["bob,50,1200,mtv"]

Only Bob’s transaction is invalid due to amount > 1000. Alice’s transaction is under the amount limit and has no conflicting transaction with the same name in a different city.

These examples illustrate both conditions: city/time conflicts (Example 1) and amount threshold (Examples 2 and 3). Next, we’ll discuss how to approach solving this problem.

Hints for Solving the Problem

Parse the Transactions: Start by splitting each transaction string by commas to easily access the name, time, amount, and city fields. Converting time and amount to integers will make comparisons easier.
Check Amount First: Any transaction with amount > 1000 is invalid outright. These can be flagged immediately without further checks.
Group by Name: The city/time comparison only matters for transactions with the same name. It’s helpful to group transactions by name (using a hashmap/dictionary) so you only compare a transaction with others of the same name.
Time Window Logic: For transactions with the same name, determine if any two occur within a 60-minute window in different cities. Consider sorting transactions by time for each name, or iterating through them and checking time differences.
Mark Both Transactions: If two transactions conflict on the 60-minute/city rule, both should be marked invalid. Be careful to flag each involved transaction.
Avoid Duplicates in Output: Ensure each invalid transaction appears only once in the result list, even if it meets the invalid criteria in multiple ways or with multiple other transactions.

Using these hints, try to sketch an approach before looking at the full solution. Next, we'll discuss step-by-step approaches, from a brute-force solution to an optimized strategy.

Approach 1: Brute Force (Basic Iteration)

Idea: A straightforward approach is to compare each transaction with all others to check for the invalid conditions. This means a double loop through the list of transactions. While this is not the most efficient solution, it’s conceptually simple and within the problem’s input size limits.

Steps:

Parse All Transactions: Go through the list and parse each transaction string into a structured format (for example, a tuple or object with name, time, amount, city). This makes data access easier.
Initialize Invalid Markers: Create a list or set to keep track of which transactions are invalid.
Check Amount Rule: Loop through each transaction:
- If its amount > 1000, mark it as invalid (add its index or identifier to the invalid set).
Check City/Time Rule: Use a nested loop to compare every pair of transactions:
- For each transaction i, compare with another transaction j (where j != i).
- If name[i] == name[j] and city[i] != city[j] and |time[i] - time[j]| <= 60, then mark both transactions i and j as invalid.
- (The absolute time difference <= 60 accounts for transactions within the same hour or less.)
Collect Results: After these checks, gather all transactions that have been marked invalid and return them (using their original string format).

Example (Brute Force): Suppose we have ["alice,20,800,mtv", "alice,50,100,beijing"]. After parsing, we compare:

Transaction0 (alice @ mtv, 800, t=20) with Transaction1 (alice @ beijing, 100, t=50):
- Same name "alice", different cities ("mtv" vs "beijing"), time difference 30 minutes – this meets the invalid criteria. So we mark both transactions 0 and 1 as invalid.
No other pairs to compare. We also check amounts: neither 800 nor 100 exceeds 1000, so amount rule didn’t mark anything initially. Finally, we output both transactions as invalid.

Complexity: The brute-force approach uses two nested loops for the city/time check, resulting in O(n²) time complexity in the worst case (where n is the number of transactions). With n <= 1000, this could mean up to ~1,000,000 comparisons, which is manageable. Space complexity is O(n) for storing parsed data and flags for invalid transactions.

Pros: Easy to implement and understand. Directly follows the problem definition.
Cons: Redundant comparisons – transactions with different names are compared even though they can never invalidate each other. We can do better by narrowing the comparisons.

Approach 2: Optimized Using HashMap (Grouping by Name)

Idea: We can optimize by only comparing transactions that have the same name. Using a hash map (or dictionary) to group transactions by the person’s name helps limit the scope of comparisons. This avoids unnecessary checks between unrelated transactions and makes the algorithm more efficient in practice.

Steps:

Parse and Group: Iterate through each transaction string, parse it into components (name, time, amount, city), and store it in a hashmap keyed by the name. For example, all transactions by "alice" will be in one list, "bob" in another, etc.
Flag Amount Violations: While grouping, or in a separate pass, mark any transaction with amount > 1000 as invalid immediately.
Check Transactions Per Name: For each name in the hashmap:
- Retrieve the list of that person’s transactions. It may help to sort this list by time (ascending order) so that time-based comparisons are easier.
- Use a nested loop (or two-pointer technique) within this list to find any two transactions that occurred within 60 minutes of each other in different cities.
  - One way: for each transaction in the list, compare it with all other transactions of the same name (either all, or just those within a 60-minute window if sorted by time). If you find a pair that satisfies the time difference ≤ 60 and city differs, mark both as invalid.
  - If the list is sorted by time, you can break out of the inner loop early once the time difference exceeds 60 minutes (since further ones will only have larger differences).
Collect Results: Compile all transactions marked invalid into the result list (using their original string representations).

Why This is Better: By grouping by name, we never compare transactions with different names, eliminating a lot of unnecessary checks. For example, if there are 500 transactions by "alice" and 500 by "bob", the brute force would do 500×500 comparisons between Alice and Bob transactions that are irrelevant. The grouped approach would handle Alice and Bob separately, focusing only on meaningful comparisons.

Example (Optimized): Consider the input ["alice,20,800,mtv", "alice,50,100,beijing", "bob,50,1200,mtv"]. After parsing and grouping:

Group "alice": [(name=alice, time=20, amt=800, city=mtv), (name=alice, time=50, amt=100, city=beijing)]
Group "bob": [(name=bob, time=50, amt=1200, city=mtv)]

We mark Bob’s transaction invalid immediately due to amount 1200 > 1000. Then check group "alice":

Sort by time (already sorted in this case: 20 then 50).
Compare Alice’s transactions: 20@mtv vs 50@beijing → 30 minutes apart, different cities, so mark both as invalid.

Group "bob" has only one transaction (we already flagged it by amount). Finally, we gather all invalid transactions: "alice,20,800,mtv", "alice,50,100,beijing", and "bob,50,1200,mtv".

Complexity: In the worst case, if all transactions have the same name, we still have a double loop among ~1000 items (so O(n²)). However, if transactions are spread across different names, the workload is split among groups. For example, if there are k names each with ~n/k transactions, the time complexity is roughly the sum of (n/k)² for each group, which is less than n² when k > 1. Additionally, sorting each group by time costs O(m log m) per group (where m is the group size), which in total is O(n log n) across all transactions. Overall, this approach is effectively O(n²) in worst-case time and O(n) space, similar to brute force in Big-O notation, but with a lower constant factor and often much faster in practice due to skipping irrelevant comparisons.

Pros: Avoids comparing transactions of different names. The logic is clearer by focusing on one name at a time. Easy lookups of transactions by name using the hashmap.
Cons: Still uses nested loops for checking the 60-minute rule (though confined to smaller groups). Given the input size, this is usually acceptable. There’s also the overhead of storing transactions in the hashmap and possibly sorting, but that's minor for n=1000.

Code Implementation

Below are implementations of the solution in both Python and Java. Both use the optimized grouping approach discussed above. The code includes a main method (or equivalent) to demonstrate how it can be executed with example input.

Python Code Implementation

Python3

. . . .

Explanation: The Python code first parses and groups the transactions. It then iterates through each group, checks the amount rule (amount > 1000) and the 60-minute rule by comparing within the group. Notice that we break out of the inner loop early when the time difference exceeds 60, thanks to sorting – this small optimization avoids unnecessary checks. We use a set for invalid_set to avoid duplicates, and finally return the list of invalid transactions.

Java Code Implementation

Java

. . . .

Explanation: The Java solution follows a similar approach. We use a Map<String, List<String[]>> to group transactions by name, where each transaction is stored as an array of its components (including the original string for output). After grouping and sorting by time, we loop through each transaction and compare it with others in the same group. We add invalid transactions to a Set (to avoid duplicates) and finally convert it to a list. The main method demonstrates the function with a sample input.

Complexity Analysis

Brute Force Approach: Time complexity is O(n²), since we potentially compare every pair of transactions (for n transactions). In the worst case (n = 1000), that’s about 1,000,000 comparisons, which is acceptable. Space complexity is O(n) for storing parsed transactions and flags for invalid ones.
Optimized HashMap Approach:
- Time Complexity: Worst-case still O(n²) (if all transactions have the same name or fall into one group). However, with multiple names, the comparisons are divided among groups, often reducing the total checks. Additionally, sorting transactions by time adds an O(n log n) component (or sum of m log m for each group of size m). In practice, this approach is much faster than brute force for data sets with varied names. For n = 1000, the difference might not be huge, but conceptually it's more efficient by cutting unnecessary comparisons.
- Space Complexity: O(n) extra space. We store transactions in a hashmap by name, which in total holds all transactions (plus some overhead for structure). We also use a set to collect invalid transactions, which in worst case could hold up to n elements.
Auxiliary complexity: Both approaches use additional space for parsing and storing results, but these are linear in the number of transactions. The primary difference is in time due to how many comparisons are made.

In summary, both approaches have similar worst-case complexity, but the optimized approach is typically faster for many real-world cases. Given the input size limit of 1000, even the brute-force approach runs efficiently, which is why this problem is manageable despite the quadratic complexity.

Step-by-Step Walkthrough of an Example

Let's walk through a representative example to see how the solution flags invalid transactions. Consider the following list of transactions:

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

We will trace the optimized approach logic (grouping by name):

Parsing and Grouping: We split each string:
- "alice,20,800,mtv" -> name="alice", time=20, amount=800, city="mtv"
- "alice,50,100,beijing" -> name="alice", time=50, amount=100, city="beijing"
- "bob,50,1200,mtv" -> name="bob", time=50, amount=1200, city="mtv"
Grouping by name:
- alice: [(20, $800, "mtv"), (50,$ 100, "beijing")]
- bob: [(50, $1200, "mtv")]
Flag Amount > 1000: We check each transaction's amount:
- Alice's transactions: 800 and 100 – both are <= 1000, so no flag yet.
- Bob's transaction: 1200 – this exceeds 1000, so we mark "bob,50,1200,mtv" as invalid.
At this point, invalid_set = { "bob,50,1200,mtv" }.
Check 60-minute Rule (Name by Name):
- For "alice": We have two transactions. Sort by time (they are already sorted: 20 then 50).
  - Compare Alice@20 (mtv) with Alice@50 (beijing):
    - Time difference = 30 minutes (50 - 20 = 30) which is ≤ 60.
    - City difference = "mtv" vs "beijing" (they are different).
    - Same name = both "alice".
    - All conditions for the rule are met, so we mark both transactions as invalid.
    - We add "alice,20,800,mtv" and "alice,50,100,beijing" to invalid_set.
  - There are no more pairs to check for "alice" (only two transactions).
- For "bob": Only one transaction in this group, so no pair to compare for the 60-minute rule.
Collect Results: Now invalid_set = { "bob,50,1200,mtv", "alice,20,800,mtv", "alice,50,100,beijing" }. We convert this set to a list. The final output (order can vary) might be:

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

Each of these transactions is flagged:

"alice,20,800,mtv" is invalid because of another "alice" transaction within 60 minutes in a different city (the one at time 50 in Beijing).
"alice,50,100,beijing" is invalid for the same reason (other transaction at time 20 in MTV).
"bob,50,1200,mtv" is invalid because its amount 1200 > 1000.

This walkthrough demonstrates how we systematically apply the rules. We handled the amount rule first, then the 60-minute rule by grouping names, which made the comparisons straightforward.

Common Mistakes and Pitfalls

Beginner solutions might run into a few common pitfalls:

Incorrect Time Difference Calculation: Make sure to use absolute difference (abs(time_i - time_j)) and check <= 60 (inclusive). A mistake here could miss transactions exactly 60 minutes apart or count those slightly over 60 by accident.
Forgetting the City Condition: Both name and different city are required for the 60-minute invalidation rule. Some might incorrectly mark transactions invalid just because they are within 60 minutes, without checking the city difference.
Not Marking Both Transactions: If transaction A makes transaction B invalid (due to the same name, different city, within 60 min), remember that transaction B also makes A invalid. Ensure you add both to the invalid list/set. Missing this can cause one of the pair to be left out.
Duplicate Entries in Output: If a transaction violates both rules or pairs with multiple others, your logic might try to add it multiple times. Using a set or checking before adding prevents duplicate output entries. (However, if the same exact transaction string appears multiple times in the input as separate entries and each is invalid, they should each appear in the output. This is about not listing the same index twice, not about filtering out identical strings from different indices.)
Parsing Errors: Not trimming spaces or assuming a certain format can cause parsing issues. Use reliable string splitting and convert numeric fields to integers for comparisons.
Considering Unrelated Transactions: Ensure you don't flag transactions that have the same city within 60 minutes (which is not invalid by city rule) or same name but outside 60-minute window. It’s a common logic error to oversimplify the condition.

By carefully following the problem conditions and systematically checking them, these mistakes can be avoided.

Edge Cases to Consider

Be sure to test and consider edge scenarios, such as:

Single Transaction: If there is only one transaction and its amount is ≤ 1000, the result should be an empty list (no other transaction to conflict with, and amount is fine). If the amount is > 1000, then that single transaction is invalid.
Same City Transactions: Multiple transactions with the same name in the same city should not invalidate each other based on the 60-minute rule. For example, ["alex,10,500,tokyo", "alex,15,300,tokyo"] – even though these are within 5 minutes, they are in the same city, so they are valid (unless amount rule triggers).
Exactly 60 Minutes Apart: Transactions exactly 60 minutes apart (difference == 60) in different cities do count as invalid. For instance, "alice,0,100,mtv" and "alice,60,200,beijing" should be flagged (60 minutes apart, different cities).
Different Names: Transactions with different names never affect each other. Ensure that no logic inadvertently crosses names. For example, "alice,30,100,mtv" and "bob,40,900,paris" have no effect on each other.
Multiple Conflicts: A transaction can be invalid for multiple reasons. E.g., "charlie,20,1200,prague" (amount too high) and "charlie,50,1300,london" are each invalid by amount, and also invalidate each other by the 60-minute/city rule. The output should list each transaction only once.
Duplicate Transaction Entries: If the input list contains identical transaction strings as separate entries, treat them as separate transactions. For example, ["dave,10,1000,mtv", "dave,10,1000,mtv"] – these two are in the same city and time, so they don't invalidate each other by city rule, and amount is exactly 1000 (not over), so neither is invalid. However, if it were ["dave,10,1001,mtv", "dave,10,1001,mtv"], both entries would be invalid due to amount > 1000, and you should return both.
Large Input Size: Although 1000 isn't very large, ensure your solution still runs efficiently at the upper limit. The brute force will work within a second or two for 1e6 checks, and the optimized solution will be even faster on average.

Considering these edge cases will help ensure your solution is robust and correct for all inputs.

This problem is essentially about detecting certain patterns in a list of timestamped events. Here are some variations and related problems to practice and deepen understanding:

Different Time Window or Conditions: Imagine changing the 60-minute window to another value, or requiring more complex conditions (e.g., transactions in three different cities within an hour). The approach of grouping by name and sorting by time would still be applicable with minor modifications.
Alert Using Same Key-Card Three or More Times in One Hour (LeetCode 1604): This is a similar pattern problem. You have a list of keycard swipe times for individuals and need to identify those who used the card 3+ times in a one-hour period. The strategy involves grouping by person and checking time windows (sliding window technique) – conceptually similar to grouping transactions by name and checking a time range.
Contains Duplicate II (LeetCode 219): While a different context (checking if any number appears at least twice within k indices in an array), it also involves checking pairs within a certain index distance. It can be solved with a sliding window or hash set approach to maintain a window of size k, somewhat akin to maintaining transactions within 60 minutes.
Log Processing Problems: In interview and coding challenges, there are problems about processing logs or transactions to find anomalies (e.g., too many requests from one user in a short time). They often use similar techniques: grouping entries by an identifier and checking time differences. Practicing such problems will reinforce the patterns used in Invalid Transactions.
Two-Pointer or Sliding Window Techniques: The optimized approach here is essentially a form of sliding window on time (within each name's list of transactions). Problems that involve finding subarrays or intervals with certain conditions (like sum, distinct elements, etc.) can help build intuition for moving window approaches.