implementation
Hashing & Frequency Maps
The pattern behind a huge share of array and string problems: use a hash map to trade memory for speed, turning O(n²) searches into O(n) single-pass solutions.
The Core Pattern
A hash map (Python dict or set) provides average O(1) lookup. When you find yourself reaching for a nested loop to check "does X exist in the data?", a hash map usually collapses that to a single pass.
When to reach for it:
- Checking membership repeatedly
- Counting element frequencies
- Grouping elements by a key
- Finding pairs or complements
Counter for Frequencies
Counter builds a frequency map from any iterable in O(n):
defaultdict for Grouping
When building adjacency lists or grouping items, defaultdict avoids the "check before insert" boilerplate:
Prefix Sums for Range Queries
Store cumulative sums so any subarray sum is O(1) after O(n) preprocessing:
The hash map seen turns a three-pointer O(n²) scan into a single pass.
When a Hash Map Is the Wrong Trade
The whole pattern is "spend memory to save time," so it stops paying off exactly when memory is the scarce resource — a stream too large to hold, or a memory-constrained environment. It also throws away order: if the problem needs sorted output or relies on the data already being sorted, a two-pointer scan over the sorted array is O(1) extra space and often clearer than a map. And it assumes hashable, exactly-comparable keys — floating-point values and "approximately equal" matches don't belong in a hash map at all.