Why does storing each scanned value's index in a hash map find a matching pair in one pass?

## The shape of the problem A support team is reconciling a day of payment records. A customer disputes a single total, and you must find whether two of that day's refunds add up to it, reporting which two records they are. The obvious approach compares every record with every later record: n(n-1)/2 comparisons, O(n^2) time, O(1) extra space. On a day with a hundred thousand records that is about five billion comparisons. ## Why hashing collapses the inner loop The inner loop is doing something wasteful: it *searches* for a value it could have *computed*. At record `i`, the partner that would complete the pair is exactly `target - amounts[i]`. There is only one such number. So the question stops being "which of the remaining records pairs with this one?" and becomes "has the number `target - amounts[i]` already gone past me?" — a membership question, which is precisely what a hash-based structure answers in expected O(1). One pass, then: 1. Compute `need = target - amounts[i]`. 2. Ask the map whether `need` was already recorded. If yes, you have your pair, and the map hands you the earlier record's index. 3. Otherwise record `amounts[i] -> i` and move on. Each record is touched once and does a constant expected amount of work, so the whole scan is O(n) expected time. ## Why a map and not a set This is the leaf's central discrimination. A hash set of the amounts seen so far would answer step 2's *yes/no* perfectly well — if all you must report is "such a pair exists", a set is the right structure and it stores less. But the requirement here is to name the two records, and the position of the earlier one is data that has to travel with the value. That makes it a map from value to index. Choose by the output the caller needs: a boolean answer takes a set; an answer that identifies the participants takes a map. ## The ordering bug this question is really about The single most common defect is inserting the current value before testing for its partner. If a record's amount is exactly half the target, then `need` equals `amounts[i]`, and a map that already contains the current record reports a match — with itself. The scan claims a pair of one record. Looking up first and inserting afterwards makes the invariant explicit: **the map contains exactly the records strictly before `i`**, so any hit is necessarily a different record. State that invariant out loud; it is what an interviewer is listening for. ## Duplicates are fine, and it is worth saying why When two records share the same amount, the second insertion overwrites the first index for that value. That does not break correctness. The invariant only requires that the stored index belongs to *some* record strictly before the current one, and any occurrence of the value satisfies the sum. It matters only if the requirement is "report the earliest such pair" — then you insert only when the key is absent, preserving the first index — or "report all pairs", which needs a map from value to a list of indices and care not to emit the same pair twice. ## Costs, stated in the right direction | Approach | Time | Extra space | Reports which records | | --- | --- | --- | --- | | Nested scan | O(n^2) worst and typical | O(1) | yes | | Value-to-index map, one pass | O(n) expected | O(n) | yes | | Value-only set, one pass | O(n) expected | O(n) | no, existence only | Two precision points. First, the O(n) time is **expected**: it assumes the hash spreads the amounts well. Adversarially chosen keys that all collide degrade lookups to linear and the whole scan to O(n^2), which is why hash-based scans over attacker-controlled input want a randomized or keyed hash. Second, the extra space is genuinely O(n) — the map can end up holding every record's amount. Calling it O(1) because "there is only one map" is a classic mis-statement; the space complexity is the size the map reaches, not the number of variables you declared. Also note what the map buys you is a one-pass algorithm, not merely a faster one: you never need the full input in advance, so the same structure works on a stream of records arriving over time. ## What to say when asked Name the transformation — a search becomes a computation plus a membership test — state the invariant that the map holds only earlier records, justify map-over-set by the required output, and quote O(n) expected time and O(n) space with the worst-case caveat.