Abstract / Summary

Identify transactions that are invalid due to names with uppercase letters or amounts that are nonpositive or not multiples of 100.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 31% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Sorting
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single method invalidTransactions. The method receives a list of transaction strings, each formatted as "name,time,amount,city". Its purpose is to return all transactions that are considered invalid according to two rules: an amount greater than 1000, or two transactions with the same name that occur within 60 minutes of each other in different cities. The algorithm groups transactions by name, sorts them chronologically, then scans each group to flag violations.

Extraction and Grouping

The first phase parses each input string and stores the parsed fields in a dictionary keyed by the transaction name. The code uses a defaultdict(list) to accumulate tuples that contain the numeric time, numeric amount, city string, original index, and the original transaction string.

tx = defaultdict(list)
for i, t in enumerate(transactions):
    name, time, amount, city = t.split(",")
    tx[name].append((int(time), int(amount), city, i, t))

By keeping the original index (i) together with the raw transaction (t), the method can later reconstruct the result in the original order without additional look-ups.

Chronological Ordering

Before checking for cross-city conflicts, each name-specific list is sorted by the transaction time. This guarantees that later scans can rely on monotonic time values.

for name in tx:
    tx[name].sort()

Sorting enables an early-exit condition in the nested loop, because once the time difference exceeds 60 minutes, no further transactions in that list can violate the time window.

Amount Threshold Check

During the scan of each sorted list, the algorithm first evaluates the simple amount rule. If the amount exceeds 1000, the corresponding entry in the invalid boolean array is set to True.

if amount > 1000:
    invalid[id] = True

The boolean array invalid is pre-allocated with the same length as the input list, allowing constant-time updates.

Cross-City Conflict Detection

The core of the validation logic is a double loop that compares each transaction with later ones in the same name group. The inner loop stops as soon as the time gap exceeds 60 minutes, thanks to the sorted order.

for j in range(i + 1, len(tx[name])):
    time2, amount2, city2, id2, t2 = tx[name][j]
    if time2 - time > 60:
        break
    if city2 != city:
        invalid[id]  = True
        invalid[id2] = True

When a city mismatch is found within the 60-minute window, both transactions are marked invalid. The early break prevents unnecessary comparisons beyond the relevant time horizon, reducing the number of iterations dramatically for long transaction histories.

Edge Cases Handled

The implementation naturally accommodates several subtle scenarios:

• Transactions that share the same name and exact timestamp are still compared because the inner loop starts at i + 1. If the cities differ, both are flagged.
• A transaction that exceeds the amount limit is marked invalid regardless of any city or time considerations; the later city check does not override this decision.
• When multiple transactions occur within the 60-minute window, the algorithm flags every pair that violates the city rule, ensuring that all involved entries become invalid.
• If a name appears only once, the inner loop never executes, and only the amount rule can affect validity.
• The use of the original index preserves the original ordering of the output, even after sorting by time for internal processing.

Performance Optimizations

Two primary techniques improve the runtime characteristics:

• Grouping by name reduces the problem size for each inner scan, avoiding a global O(N²) comparison across all transactions.
• Sorting each name group and breaking out of the inner loop once the time difference exceeds 60 minutes eliminates needless checks for distant transactions. This transforms the inner loop into a sliding-window scan, which is much faster for dense time clusters.

The boolean invalid array provides O(1) access for marking and later filtering, and the final list comprehension extracts the flagged transactions in a single pass.

return [t for i, t in enumerate(transactions) if invalid[i]]

Imagine a big notebook filled with lists of people buying things in different cities. Each entry shows who bought something, when they bought it, how much it cost, and which city they were in.

The computer starts by organizing everyone into groups so that all of a person’s records are kept together in one place. It sorts these records by time so it can look at them in order from the earliest to the latest.

Then the computer goes through each group to look for trouble. First, it peeks at the price of every item. If any single item costs more than one thousand dollars, the computer puts a special mark next to that record to show it is suspicious.

Next, it checks if the same person traveled to a different city very quickly. It looks at the time between two shopping trips. If the time difference is less than sixty minutes and the cities are different, it means the person could not possibly have traveled that fast between them. The computer flags both of those trips as suspicious because it is impossible to be in two places at once in such a short time.

After looking at every single person and every single trip, the computer gathers up all the records that have a suspicious mark and shows them to you.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java				TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java			Go
	Progiez	C++	Python	Java
github	black-shadows	C++
	charles-wangkai			Java
	fsq	C++
	JoshCrozier				JS
	lkwq007		Python
	suxrobGM					C#
	varunu28			Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality