dsa · coding · phone-screen
Two Sum & Hash-Map Lookup Pattern
Trade space for time using a hash map to convert O(n²) pair-finding into O(n) single-pass lookups. Foundation pattern behind dozens of LC problems.
Theory
Explanation
Intuition first, formal definition second. Skim the bullets if you already know this; read the prose if you don't.
Pairs are quadratic by default, n² to test every pair. A hash map lets you ask "have I already seen the partner I need?" in O(1), turning a two-pass nested loop into one linear sweep. The trick is to store what you have seen so far, not what is ahead.
For each element x you scan, compute the complement (target − x). If the complement exists in the map, you have found a pair. Otherwise, record x in the map keyed by its value (mapping value → index). This generalizes to any "find a pair / triple / k-tuple satisfying a predicate" problem where the predicate can be inverted into a complement.
When to use
Unsorted input, single-pass acceptable, lookup-by-value cheap, average O(n) needed. Works for sum / difference / xor predicates and similar inversions.
When not to
When the array is already sorted (two-pointer is O(1) extra space). When you need to return all pairs and duplicates matter (hash collapses). When memory is constrained (embedded targets) and n is small, nested loop may be faster in practice.
Time: O(n) average · Space: O(n)
Key insights
- Store value → index, not index → value, you query by value.
- Check map BEFORE inserting current element, otherwise self-pairs (x + x = target) double-count.
- Hash collisions degrade to O(n²) worst case in adversarial inputs (rare in interviews but worth naming).
- Generalizes to k-sum via recursion: each level fixes one element then reduces to (k−1)-sum on the rest.
- For "count of pairs" variants, accumulate counts in the map values instead of indices.