A hash map (dictionary) stores key-value pairs and supports insert and lookup in O(1) on average. It is the single most useful tool for turning an O(n²) 'compare every pair' brute force into an O(n) solution.
Remember what you have seen
As you scan once, store each element (or its count) in a hash map. Then any 'have I seen X?' or 'how many of X?' question is answered instantly, without a second loop.
Two Sum in one pass
seen = {} // value -> index
for i = 0 to n-1:
need = target - A[i]
if need in seen: return (seen[need], i)
seen[A[i]] = iO(n) average→O(n)
One pass; the map can hold up to n entries.
⚡ The edge
- Whenever the brute force is 'for each element, scan the rest' (O(n²)), ask: can a hash map remember what I've already seen and make the inner scan O(1)?
- Use a map for counts and a set when you only need membership (have I seen this before?).
Worked example
Find two numbers in [2, 7, 11, 15] that add to 9.
- Scan once, asking for each number what partner it needs: 9 - 2 = 7.
- Store 2 in the map. Next is 7; it needs 9 - 7 = 2, which is already in the map.
- So 2 and 7 form the pair — found in a single pass.
Answer: 2 and 7 (indices 0 and 1), in O(n)
Worked example
Find the first non-repeating character in 'aabbcde'.
- First pass: count each character -> a:2, b:2, c:1, d:1, e:1.
- Second pass in order: a (2) repeats, b (2) repeats, c (1) does not.
- So 'c' is the first character with a count of one.
Answer: 'c' (two passes, O(n))
⚠ Watch out
- Hash operations are O(1) average, but O(n) in the rare worst case of many collisions.
- A hash map uses O(n) extra memory — the price for the speed-up.
- Keys must be hashable and stable; don't use a changing object as a key.