Arrays
Two pointers, sliding windows, prefix sums and hash maps — the patterns behind most array problems
Arrays are where almost everything 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.
What an Array Actually Looks Like
An array is one continuous block of memory, divided into equal-sized slots.
Two things follow from "one continuous block", and between them they explain every array technique.
Why reading any index is instant
The computer knows where the block begins and how wide each slot is. So it does not search — it calculates:
address of nums[i] = start address + i × slot sizeOne multiplication and one addition, whatever i is. nums[999999] costs precisely what nums[0] costs. That is O(1) random access — "random" meaning any position, in any order, at the same price.
This is why indices start at 0
The index is not a counter, it is a distance from the start. The first item is 0 slots away from the beginning, the second is 1 slot away.
Once you read nums[i] as "i slots along" rather than "the i-th thing", off-by-one errors get noticeably rarer.
Why inserting is expensive
The slots must stay adjacent with no gaps — that is what makes the address arithmetic work. So making room in the middle means physically moving everything after it.
The consequence you will actually meet
Removing items from the front of a list inside a loop turns an O(n) algorithm into O(n²) — every removal quietly shifts the entire rest of the array.
Python's list.pop(0) and JavaScript's Array.shift() are exactly this trap. Use collections.deque or an index that moves instead. See stacks and queues.
The trade, in one table
| Operation | Cost | Why |
|---|---|---|
Read or write nums[i] | O(1) | Address arithmetic |
| Append at the end | O(1)* | Nothing to move |
| Insert or delete in the middle | O(n) | Everything after shifts |
| Insert or delete at the front | O(n) | Everything shifts |
| Search an unsorted array | O(n) | Must check each slot |
| Search a sorted array | O(log n) | Binary search |
* Amortised. The block occasionally fills up, and then the whole thing is copied to a bigger one. That copy is O(n), but it happens rarely enough that the average stays O(1).
Read that table as a set of instructions: you have a fast operation and a slow one, so build solutions out of the fast one. Every pattern below does exactly that — two pointers, sliding windows and prefix sums all read freely and never shift anything.
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.