Arrays and hashing

A refund paid twice

Every night at 1 a.m. a payments job sends the day's refunds to the bank. It has one rule: never refund the same order twice. The code enforces the rule the obvious way. For each refund, it looks at every refund before it and compares order ids.

At 40,000 refunds a night that is 800 million comparisons, about 80 seconds in Python. Nobody noticed. Then a sale pushed the count to 300,000. Do the sum before reading on. 300,000 × 300,000 ÷ 2 is 45 billion comparisons. At roughly 10 million a second, 75 minutes. The bank collects the file at 1:30 whether the job has finished or not. That is how a customer in Pune was refunded ₹1,250 twice.

The reflex is a faster machine. Ten times faster is still seven and a half minutes, and next year's sale will be bigger. A faster machine does not fix it because the job is asking the wrong question. Each refund asks "is it this one? this one?" of every refund before it, when the only thing it needs to know is: have I seen this order id before?

Pause and predict What should the job carry as it walks, so each refund is checked in one step?

Why a set answers in one step

Take a paper register of 600 names, where you must answer "is this name in it?" many times an hour. Reading all 600 each time is the refund job. A better register gives each first letter its own page. "Rao" goes to page R, which holds eleven names; read eleven, done. With 6,000 names you give the crowded letters more pages, so every page stays short.

A hash set is that register. The hash function turns a key into a page number, a bucket, without looking at any other key. Python's set and Java's HashSet use a better rule than the first letter and add buckets as they fill, so a lookup reads one short bucket whether the set holds ten keys or ten million. That is what "O(1) on average" means here.

Pause and predict The set grows from 300,000 ids to 3 million. One lookup now takes:

Here is the fix most people write first.

Pause and predict Run it on last night's 300,000 refunds. How many does it hold as duplicates?

The invariant is also why the fix is correct. Take any two refunds, j before i. When the loop reaches i, j is already in the set, so the pair is caught. It is caught once, when the later one arrives. And a refund never matches itself, because it is not in the set yet.

The price is memory. 300,000 ids is about 25 MB. You spend O(n) memory to avoid a second pass over the data. That trade is the pattern. Every problem in this unit walks the input once, keeps a memory of what is behind it, and asks that memory one question per step. What changes is what you store (an id, an index, a count, a list) and the key you store it under.

The same trade appears as a cache in system design, and as the pair counts that train a tokenizer in the LLM course.

The pattern in disguise

Here are two problems that never say "hash map".

A customer splits ₹50,000 into two transfers to stay under a review limit. You have their 3,000 transfers, unsorted. Which two add to exactly ₹50,000? It is the refund job with one change: for each amount x, ask the set whether you have seen 50,000 − x, the partner, instead of x itself. Interview sites call it Two Sum.

A food app wants a "your usual" button, so orders with the same items in any order should count as one basket. Here the key is the hard part. Two baskets must get the same key exactly when they are the same basket.

Pause and predict Three candidate keys for a basket. Which one wrongly puts different baskets together?

Three that only look like it

• Sorted input and O(1) space: the order already does the set's job. That is two pointers.
• A contiguous range with a sum: still a map, but of running totals, not values. That is prefix sums.
• The k most frequent: count with a map, then pick with a heap or buckets. Counting is this unit; picking is heaps.

Where it bites

A Java port of the refund job compared the amount in the ledger with the amount in the bank's file, both read from maps keyed by order id. Every test passed; the test amounts were 50 and 100. The first night in production, every amount above 127 was flagged as a mismatch.

Pause and predict Both maps hold "A17" → 1250. What does ledger.get("A17") == bank.get("A17") give?

Four more.

• Inserting before looking up. The map already holds i, so 3 + 3 = 6 pairs a single 3 with itself. Ask, then remember.
• A key without value equality. In Java an int[] key compares by identity, so no two words ever share a group. Turn it into a String. In Python a list cannot be a key; use a tuple.
• Walking from every value in Longest Consecutive Sequence: O(n²) on one long run. Start only from a value with no left neighbour.
• Sorting when the answer needs positions. Sorting loses the original indices that Two Sum returns.