Card 08/ 08
Recap: Hash Map Patterns
A map of what came before turns a search into a lookup: complements, counts, canonical keys, and the array as its own map.
A hash map pattern keeps a map of what came before, so a search inside a loop becomes one lookup: O(n) on average for n items, against O(n²) for checking every pair, with O(n) extra space. Each lookup is O(1) on average and O(n) in the worst case.
The template computes the key the current item needs, looks it up, and only then records the item. That order keeps the invariant that the map holds only earlier items, so no item pairs with itself, and two equal values can still form a pair. The cue is a property, not a word: each item needs something decided by the items already seen.
| Cue | What the map holds | Example |
|---|---|---|
| Each item needs a partner among the earlier items | Each earlier value, with its index | Two prices that add up to a budget |
| Two collections must hold the same items in any order | A count of each item | Two delivery manifests |
| Items that should count as equal must be grouped | A list of items under each canonical key | Melodies grouped by the steps between notes |
| Values lie in 1 to n | Nothing: index v − 1 is the slot for v | The missing and doubled seat number |
The key decides what counts as equal. It must come out the same for every item that should match and differ otherwise: sorted letters or letter counts for anagrams, the steps between notes for melodies, never a sum that two different items can share. When the input is already sorted, two pointers find a pair in O(1) extra space, and that is the next pattern.
← → move through sections and cards