Invalid Transactions: Hash Map Grouping Pattern

You are given a list of transaction strings, where each string looks like "name,time,amount,city". Your job is to return all the invalid ones. A transaction is invalid if the amount exceeds 1000, or if there is another transaction with the same name within 60 minutes in a different city. Both conditions are checked independently.

This is LeetCode 1169: Invalid Transactions.

Example: transactions = ["alice,20,800,mtv","alice,50,100,beijing","bob,50,1200,mtv"]

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

All three are invalid. The first two alice transactions happen within 30 minutes of each other in different cities. Bob's transaction has amount 1200, which exceeds 1000.

Why this problem matters

This problem combines three skills that show up constantly in interview questions: string parsing, hash map grouping, and pairwise comparison. None of those ideas are individually hard. The challenge is gluing them together cleanly without getting tangled in off-by-one errors or duplicate results.

It is also a great example of a problem where the brute force approach (comparing every pair of transactions) is not terrible. The input constraints are small enough that O(n^2) works. But grouping by name first makes the code cleaner and faster in practice, and it teaches a pattern you will reuse on harder problems.

The key insight

The second invalidity condition only applies to transactions with the same name. That means you do not need to compare every transaction against every other transaction. You only need to compare transactions within the same name group.

This is the classic hash map grouping pattern: build a map from name to list of transactions, then process each group independently.

The algorithm is:

1. Parse each transaction string into its four fields: name, time, amount, city
2. Group all parsed transactions by name using a hash map
3. For each transaction, check if amount exceeds 1000 (instant flag)
4. For each transaction, compare it against every other transaction in its name group. If two transactions have different cities and their times are within 60 minutes, flag both
5. Use a set of indices to avoid duplicate results
6. Return the original strings for all flagged indices

The solution

def invalid_transactions(transactions):
    parsed = []
    for i, t in enumerate(transactions):
        name, time, amount, city = t.split(",")
        parsed.append((name, int(time), int(amount), city))

    groups = {}
    for i, (name, time, amount, city) in enumerate(parsed):
        if name not in groups:
            groups[name] = []
        groups[name].append(i)

    invalid = set()
    for i, (name, time, amount, city) in enumerate(parsed):
        if amount > 1000:
            invalid.add(i)
        for j in groups[name]:
            if i != j:
                _, time_j, _, city_j = parsed[j]
                if abs(time - time_j) <= 60 and city != city_j:
                    invalid.add(i)
                    invalid.add(j)

    return [transactions[i] for i in invalid]

The parsing step splits each string on commas and converts time and amount to integers. The grouping step builds a dictionary mapping each name to the list of indices where that name appears. The validation step iterates through every transaction, checks the amount condition first, then loops through all transactions in the same name group to check the city-and-time condition. Using a set for invalid ensures no duplicates in the output.

Visual walkthrough

Let's trace through ["alice,20,800,mtv","alice,50,100,beijing","bob,50,1200,mtv","alice,200,400,mtv","bob,60,500,shanghai"] step by step.

Notice how the grouping step lets us skip comparing alice against bob entirely. We only look within each name group, keeping the logic focused.

Complexity analysis

Time: O(n^2) in the worst case. If every transaction has the same name, the inner loop compares each transaction against all others in that group, giving n^2 comparisons. In practice, if names are spread out, the work is much less.

Space: O(n). We store every parsed transaction and a set of invalid indices. The hash map also stores n index references across all groups.

The building blocks

1. String parsing into structured data

Splitting a delimited string into typed fields is a basic but essential skill. The pattern is always the same: split on the delimiter, then convert each piece to its proper type. You see this in log file processing, CSV parsing, and many interview problems that give you encoded input.

name, time, amount, city = t.split(",")
time, amount = int(time), int(amount)

2. Hash map grouping by key

This is the same group-by-key pattern used in Group Anagrams. You iterate through a collection, compute a key for each element, and collect elements that share the same key into a list. The only difference is what you use as the key. In Group Anagrams the key is the sorted characters. Here the key is the transaction name.

groups = {}
for i, (name, time, amount, city) in enumerate(parsed):
    if name not in groups:
        groups[name] = []
    groups[name].append(i)

Once you have this brick internalized, any problem that says "check items that share some property" should trigger the grouping reflex immediately.

Edge cases

A few things to watch for with this problem:

• Single transaction. If there is only one transaction, the city condition can never trigger (there is nothing to compare against). Only the amount check matters.
• All same city. If every transaction uses the same city, the city condition never fires. Only the amount condition matters.
• Amount exactly 1000. The problem says "exceeds" 1000, meaning 1000 itself is valid. Only amounts strictly greater than 1000 are invalid.
• Time difference exactly 60. The problem says "within 60 minutes," and the condition is abs(time_i - time_j) <= 60. So a gap of exactly 60 minutes counts as within range.
• Duplicate results. The same transaction can be flagged by both conditions (amount too high AND city conflict). Using a set of indices prevents returning it twice.
• Same name, same city, close times. This is valid. The city condition requires different cities. Two alice transactions in the same city are fine regardless of timing.

From understanding to recall

This problem feels manageable once you see the solution. Parse, group, compare. But the tricky part is not the algorithm itself. It is remembering to reach for the grouping pattern when you encounter a new problem that involves checking relationships between items that share some property.

The building block here is "group by key, then validate within each group." The key function and the validation logic change from problem to problem, but the structure stays the same. You build a map, iterate through groups, and apply your condition.

Spaced repetition helps you lock this in. You practice writing the group-by-key template from scratch at increasing intervals. After a few cycles, you stop thinking about whether to group. You just do it automatically. The decision becomes instant, freeing your attention for the harder part: figuring out what to check within each group.

Related posts

• Group Anagrams - hash map grouping pattern
• Top K Frequent Elements - frequency counting with hash maps
• Contains Duplicate - hash set for duplicate detection

The best way to get these patterns into long-term memory is not to re-read solutions. It is to practice recalling them at the right intervals. CodeBricks uses spaced repetition to help you build and retain the building blocks that make interview problems feel automatic.