Watch 10 video solutions for Invalid Transactions, a medium level problem involving Array, Hash Table, String. This walkthrough by Kelvin Chandra has 10,225 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |