Hash Maps & Sets
Beginner · 18 min read · Problem-Solving Patterns, Arrays & Strings
Trade memory for time: "have I seen this?", counting, and grouping in O(1).
A huge share of "slow" solutions have the same shape: for each element, loop over the others to find something. That inner loop is a search — and a hash map or hash set turns any search for an exact value into a single O(1) step.
The idea: remember what you've seen
A nested loop asks, for every element, "is there a partner somewhere else?" — re-scanning the array each time. Instead, walk once and store what you've passed in a hash map. Now "is the partner there?" is one lookup.
The template: check, then store
Checking before storing matters: it stops an element from pairing with itself (in Two Sum with target 6, the single element 3 must not match itself).
Worked problems
O(n) time, O(n) space. (If the array were sorted, two pointers would do it in O(1) space.)
Variations at a glance
Practice ladder
Interview questions
- When would you avoid a hash map even though it makes the solution O(n)?
- Why is the longest-consecutive-sequence solution O(n) despite the inner while loop?
Further reading
Key takeaways
- A hash map or set turns "search for a value" into one O(1) average step — the fix for most nested-loop brute forces.
- Template: walk once, check for what you need, then store what you've seen.
- Grouping problems are about choosing the key; don't use int[] as a key.
- Use int[26] for letter counts; iterate the set (not the array) when duplicates would repeat work.
- State the trade: O(n) extra space for O(n) time.