Foundations
Hash Maps
Trade space for O(1) lookups. The backbone of complement search, frequency counting, and grouping.
What is a hash map?
A hash map is a key-value store that answers "what value is associated with this key?" in O(1) average time. Python's built-in dict is a hash map. The basic operations are:
Internally, a hash function converts the key into an array index. Two keys that hash to the same index are called a collision; Python handles collisions via open addressing. If many keys collide into the same bucket the lookup degrades to a linear scan - worst case O(n). With a good hash function and a reasonable load factor, collisions are rare and the average stays O(1).
The core trade-off: hash maps give O(1) average lookup and insert at the cost of O(n) space and no sorted order. Python dicts preserve insertion order since 3.7, but the keys are not sorted by value. If you need sorted iteration or range queries, a balanced BST (or Python's sortedcontainers.SortedDict) is the right tool.
Core operations
| Operation | Average Time | Worst Case | Notes |
|---|---|---|---|
| Get | O(1) | O(n) | Collisions degrade to O(n); rare in practice |
| Put | O(1) | O(n) | Occasional resize is amortized O(1) |
| Delete | O(1) | O(n) | |
| Contains key | O(1) | O(n) | key in d |
| Iterate | O(n) | O(n) | Visits all key-value pairs |
Key patterns
Complement lookup
For each element, ask "is the element I need to pair with this already in the map?" Record each element's index (or value) as you scan forward. The inner scan collapses from O(n) to O(1), turning an O(n²) brute force into O(n).
When to use - the problem gives a target sum or difference between two elements and asks you to find the pair (two sum, a pair with a given difference). The brute force checks every pair at O(n²); the map collapses the inner search to a single O(1) lookup.
How it works - scan once and keep a map of every value you have already seen. For each new element, compute the value that would complete the pair and look it up in the map. Because you store as you go, the match - if one exists - is always an earlier element, so a single forward pass finds it. Check for the complement before you store the current element; otherwise an element can pair with itself when the target is exactly double its value. One pass, O(n) time, O(n) space.
Example: pair with a target sum, unsorted. In [4, 9, 3, 14] with target 12, the scan misses twice: 4 wants an 8 and 9 wants a 3, neither seen yet, so each value is stored with its index. Reaching 3 flips the complement to 9, which seen already holds at index 1, and the function returns [1, 2] without ever touching 14. Two misses, one hit - the visualizer below plays each step.
seen[num] = index before checking, a number can match itself when target equals double that number. The check-then-store order prevents the self-match.Frequency counting
Build a map from element to its count, then reason about counts. collections.Counter is the idiomatic tool; a plain dict with .get(key, 0) + 1 works identically. The key shift: after building the frequency map, the rest of the problem operates on counts, not on the original values.
When to use - the question is about how often values appear: "how many times does X occur", "which element is most common", "do two collections have the same multiset of items". Sorting or repeated scans to count would cost O(n log n) or O(n²); one pass over the data builds every count.
How it works - walk the input once and increment a counter for each element. After the pass the map holds every value's exact frequency, so the rest of the problem reads answers off the counts instead of re-examining the raw values. The counts are what carry the information - equal frequency maps mean equal multisets, the largest count names the mode. Building the map is O(n) time and O(k) space, where k is the number of distinct values.
Example: count every value once. One pass over [1, 1, 2, 3, 3, 3]: the second 1 bumps counts[1] to 2, the lone 2 opens a fresh entry, and the three 3s walk counts[3] up 1, 2, 3 across the last three indices. The pass ends with three distinct values, 1 -> 2, 2 -> 1, 3 -> 3, and 3 as the most frequent. The visualizer below tallies each index in turn.
Counter is a subclass of dict - you can index it with counts[key], call counts.most_common(k), and add two counters together. It returns 0 for missing keys instead of raising KeyError.Grouping by derived key
Compute a canonical form for each element - a transformed representation that is identical for all elements in the same group. Use that canonical form as the hash map key. All elements mapping to the same canonical form land in the same group.
When to use - the problem asks you to bucket items by some shared property: group anagrams, collect words by first letter, partition numbers by a modular value. Comparing every item against every other to find its group is O(n²); a derived key drops it to one O(n) pass.
How it works - for each element, compute a key that is the same for every item that belongs together and different for items that don't. For anagrams that key is the sorted characters - every anagram of a word produces the identical sorted form, so they collide into one bucket on purpose. Append each element to the list stored under its key; a defaultdict(list) creates the empty list on first access so you never special-case the first item. One pass groups everything, at the cost of computing each key.
Example: group anagrams. bin sorts to b i n and starts a group; nib sorts to the same letters and appends to that existing group. log (g l o), dot (d o t), and cat (a c t) each open new groups, and tod appends to dot's group because both sort to d o t. Six words collapse into four groups - the visualizer below derives the key for each word.
defaultdict(list) eliminates the first-element special case - without it, you need if key not in groups: groups[key] = [] before every append. defaultdict initializes missing keys automatically on first access.When to reach for a hash map
- The problem says "seen before" or "contains duplicate" - store visited elements in a set or map.
- You need to count occurrences of elements - frequency map with
Counter. - You need to find a complement or pair that satisfies a numeric condition - complement lookup.
- You need to group elements by a derived property (anagram key, first character, modular value).
- The problem requires O(1) lookup by key where a list would give O(n) search.
- You are building a cache or memo table for previously computed results.
- You need to track the first or last occurrence of something by value.
Done reading? Mark it so it sticks in your dashboard.