Browse
Arrays & Hashing
Contiguous storage, O(1) average-case lookups via hash maps, and the frequency-counting patterns they enable.
What it is
Arrays give O(1) indexed access at the cost of O(n) insertion/deletion in the middle. Hash maps (dictionaries/sets) trade that positional guarantee for O(1) average-case lookup, insert, and delete by key, using a hash function to bucket keys.
Core patterns
- Frequency counting — build a hash map of value → count in one pass, then answer queries in O(1).
- Two-sum via complement lookup — for each element, check whether
target - elementhas already been seen, avoiding the O(n²) brute force. - Grouping by a derived key — e.g. group anagrams by their sorted-character key.
Complexity caveats
Hash map operations are O(1) average case — a poor hash function or adversarial input can degrade this to O(n) worst case. Arrays keep their O(1) access and O(n) contiguous-memory cache locality regardless of input.
Why it's the starting point
Nearly every other pattern — two pointers, sliding window, even graph adjacency lists — builds on comfortably reasoning about arrays and hash-based lookups first.