Arrays
Two pointers, sliding windows, prefix sums and hash maps — the patterns behind most array problems
Arrays are where almost every algorithm interview starts, and for good reason: they force you to think about access patterns. An array gives you O(1) random access but O(n) insertion and deletion, and nearly every technique below is a way of exploiting the first to avoid paying the second.
The Four Patterns
Almost every array problem here is one of these.
1. Hash map — turn searching into looking up
When you find yourself writing a nested loop to find "the other half" of something, a hash map usually collapses it to one pass. The cost is O(n) memory.
- Two Sum — the archetype
- Contains Duplicate — presence only, so a set suffices
- Group Anagrams — keyed by a computed signature
- Top K Frequent Elements — counting, then ranking
2. Two pointers — let a sorted (or symmetric) structure guide you
Two indices moving under a rule that provably discards possibilities. The hard part is always the proof that what you skip could not have been the answer.
- Container With Most Water — converging from both ends
- Merge Sorted Array — filling from the back to avoid shifting
- Remove Duplicates from Sorted Array II — a read pointer and a write pointer
- Trapping Rain Water — two pointers plus running maximums
3. Prefix sums — precompute so range queries become subtraction
Build cumulative totals once, and any range question becomes O(1) arithmetic.
- Running Sum of 1d Array — the building block
- Find Pivot Index — total minus left gives right, for free
- Product of Array Except Self — prefix and suffix, with multiplication
4. Single-pass running state — carry the answer as you go
Keep one or two variables that summarise everything seen so far. Often a dynamic-programming table collapsed down to scalars.
- Best Time to Buy and Sell Stock — a running minimum
- Maximum Average Subarray I — a fixed-size sliding window
How to Recognise Which One
| The problem says… | Reach for |
|---|---|
| "find a pair / has this appeared before" | Hash map or set |
| "the array is sorted" | Two pointers or binary search |
| "sum of a subarray / range" | Prefix sums |
"subarray of size k" | Fixed sliding window |
| "longest / shortest subarray such that…" | Variable sliding window |
"in place, O(1) extra space" | Read and write pointers |
"k most frequent / largest" | Counting, then bucket sort or a heap |
All Problems
| Problem | Difficulty | Pattern |
|---|---|---|
| Two Sum | Easy | Hash Map |
| Contains Duplicate | Easy | Hash Set |
| Best Time to Buy and Sell Stock | Easy | Running Minimum |
| Running Sum of 1d Array | Easy | Prefix Sum |
| Find Pivot Index | Easy | Prefix Sum |
| Maximum Average Subarray I | Easy | Sliding Window |
| Merge Sorted Array | Easy | Two Pointers |
| Number of Good Pairs | Easy | Counting |
| Minimum Index Sum of Two Lists | Easy | Hash Map |
| Sort the People | Easy | Custom Sort |
| Final Value of Variable | Easy | Simulation |
| Container With Most Water | Medium | Two Pointers |
| Product of Array Except Self | Medium | Prefix & Suffix |
| Group Anagrams | Medium | Hash Map |
| Top K Frequent Elements | Medium | Bucket Sort |
| H-Index | Medium | Sorting |
| Remove Duplicates from Sorted Array II | Medium | Two Pointers |
| Trapping Rain Water | Hard | Two Pointers |
Where to start
If you are new to these, work through Two Sum, then Best Time to Buy and Sell Stock, then Container With Most Water. Those three cover hash maps, running state and two pointers — and everything else builds on them.