A transaction is possibly invalid if:
$1000, or;60 minutes of another transaction with the same name in a different city.You are given an array of strings transaction where transactions[i] consists of comma-separated values representing the name, time (in minutes), amount, and city of the transaction.
Return a list of transactions that are possibly invalid. You may return the answer in any order.
Example 1:
Input: transactions = ["alice,20,800,mtv","alice,50,100,beijing"] Output: ["alice,20,800,mtv","alice,50,100,beijing"] Explanation: The first transaction is invalid because the second transaction occurs within a difference of 60 minutes, have the same name and is in a different city. Similarly the second one is invalid too.
Example 2:
Input: transactions = ["alice,20,800,mtv","alice,50,1200,mtv"] Output: ["alice,50,1200,mtv"]
Example 3:
Input: transactions = ["alice,20,800,mtv","bob,50,1200,mtv"] Output: ["bob,50,1200,mtv"]
Constraints:
transactions.length <= 1000transactions[i] takes the form "{name},{time},{amount},{city}"{name} and {city} consist of lowercase English letters, and have lengths between 1 and 10.{time} consist of digits, and represent an integer between 0 and 1000.{amount} consist of digits, and represent an integer between 0 and 2000.Problem Overview: Each transaction is a string formatted as name,time,amount,city. A transaction becomes invalid if the amount exceeds 1000, or if another transaction with the same name occurs within 60 minutes in a different city. You must return all transactions that violate these rules.
Approach 1: Brute Force Comparison (O(n²) time, O(n) space)
Parse every transaction into structured fields: name, time, amount, and city. First mark transactions invalid if amount > 1000. Then compare every pair of transactions using two nested loops. If two entries share the same name, their time difference is ≤ 60, and their cities differ, mark both as invalid. This approach directly implements the rule definition and requires only basic iteration over an array. The downside is the O(n²) pairwise comparison, which becomes slow when the number of transactions grows.
Approach 2: Map-Based Grouping with Sorting (O(n log n) time, O(n) space)
Group transactions by name using a hash table. For each name, sort that user's transactions by time using a sorting step. After sorting, iterate through the list and check nearby transactions whose time difference is within 60 minutes. Because the list is ordered, you only compare forward while the time window is valid, avoiding unnecessary checks. Transactions with amount > 1000 are immediately flagged, while city conflicts are detected during the local window scan. Sorting reduces the number of comparisons dramatically and keeps the logic organized by user.
This map-based approach scales much better because transactions from different users never interact. Each group is processed independently, and sorting allows efficient time-window checks instead of scanning the entire dataset repeatedly.
Recommended for interviews: The brute force approach demonstrates that you understand the rule constraints and how to translate them into comparisons. Interviewers usually expect the hash map grouping solution because it reduces unnecessary comparisons and structures the problem cleanly around user-based transaction histories. Showing the optimized map + sorting approach signals strong understanding of data organization and practical performance improvements.
This initial approach involves checking each transaction to determine if it fails either of the given conditions. We'll iterate through the list multiple times to compare transactions that share the same name.
This is not the most optimal solution but it helps to ensure correctness before moving on to more optimized algorithms.
The function invalidTransactions begins by defining a helper function isInvalid to compare if two transactions are invalid due to name and city within 60 minutes. Transactions are then parsed into a dictionary for ease of comparison. Each transaction is checked if the amount exceeds 1000 or if conditions defined in isInvalid are met.
Time Complexity: O(n^2) where n is the number of transactions. We have a nested loop comparing each transaction with every other transaction.
Space Complexity: O(n), since we store each parsed transaction in a list.
This approach optimizes the brute-force solution by using maps to store transactions group by their names, which reduces unnecessary comparisons, thus improving efficiency. This greatly reduces comparisons when there are many transactions with different names.
The Java solution employs a map to efficiently group transactions by name, reducing the scope of city and time comparison to only transactions that share a name. Each group is sorted by time to minimize comparison overhead. Uniqueness in the result is ensured by converting it to a set before returning.
Java
JavaScript
Time Complexity: O(n log n) due to sorting each group of transactions by time. Each time comparison within groups is constrained to those with smaller time differences.
Space Complexity: O(n) for storing parsed transactions.
We traverse the transaction list. For each transaction, if the amount is greater than 1000, or if the transaction has the same name but different cities and the time interval does not exceed 60 minutes, then add it to the answer.
Specifically, we use a hash table d to record each transaction, where the key is the transaction name, and the value is a list. Each element in the list is a tuple (time, city, index), indicating that a transaction with the number index was conducted in the city city at the moment time. At the same time, we use a hash table idx to record the transaction number in the answer.
We traverse the transaction list. For each transaction, we first add it to the hash table d, and then judge whether its amount is greater than 1000. If so, add its number to the answer. Then we traverse the transactions in the hash table d. If the transaction names are the same but the cities are different and the time interval does not exceed 60 minutes, add its number to the answer.
Finally, we traverse the transaction numbers in the answer and add the corresponding transactions to the answer.
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the transaction list.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) where n is the number of transactions. We have a nested loop comparing each transaction with every other transaction. |
| Optimized Map-based Approach | Time Complexity: O(n log n) due to sorting each group of transactions by time. Each time comparison within groups is constrained to those with smaller time differences. |
| Hash Table + Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pairwise Check | O(n²) | O(n) | Good for understanding the rule logic or when input size is small |
| Hash Map Grouping + Sorting | O(n log n) | O(n) | Best general solution; scales well by grouping transactions per user |
1169 Invalid Transactions • Kelvin Chandra • 10,225 views views
Watch 9 more video solutions →Practice Invalid Transactions with our built-in code editor and test cases.
Practice on FleetCode