Two Pointers
⏱️ ~3-minute bite · solve the sandbox to master
5-Year-Old Metaphor
— The physical, real-world picture. No jargon.🪥 Squeezing a tube of toothpaste from both ends toward the middle.
The naive approach (what everyone writes first)
You have a sorted array [1, 3, 5, 7, 9, 11] and want to find two numbers that add to 12. The brute-force approach: pick every pair — check (1,3), (1,5), (1,7) … then (3,5), (3,7) … That's n² pairs for an O(n²) solution.
The squeeze trick (the aha moment)
Because the array is sorted, you can start at both ends and squeeze inward. Sum too big? Move the right pointer left (smaller number enters). Sum too small? Move the left pointer right (bigger number enters). The answer must lie between the pointers — or it doesn't exist.
The key invariant
After every pointer move, you eliminate an entire slice of the search space, not just one pair. Moving the left pointer right discards every pair that could form with the old left value. Because the array is sorted you know none of those pairs can be the answer — they'd all be smaller. Each step eliminates an entire row of the n² grid.
This collapses O(n²) to O(n) — both pointers together traverse the array at most once.
When to reach for two pointers
- Array is sorted (or can be sorted)
- Problem involves a pair or triplet summing to a target
- "Remove duplicates in-place", "partition", or "reverse in-place" — slow/fast pointer variant
- Palindrome check, water trapping — symmetric squeeze
⚠️ Pitfall: if the array is not sorted and sorting is not allowed, two pointers won't work — use a hash map instead (O(n) time, O(n) space).
Interactive Sandbox
— Move something, see it react instantly.🎯 Two Sum (Sorted)
target = 12Start: L=0 (1), R=5 (11). Sum=12. Found it!
Challenge
Explore all 5 two-pointer patterns. (1/5 explored)
Why Should I Care?
— The exact interview question + the bug it kills.Q — Why must the array be sorted?
The pointer-move decision relies on knowing which direction changes the sum. On a sorted array: moving the left pointer right always increases the sum; moving the right pointer left always decreases it. Without sorted order, neither direction is predictable — you can't eliminate anything, and you're back to O(n²).
Q — How does 3Sum reduce to 2Sum?
Sort the array first. Then iterate: for each element at index i (the anchor), run two-pointer on the rest of the array looking for a pair that sums to -arr[i]. The outer loop is O(n); the inner two-pointer is O(n) per anchor → total O(n²) vs naive O(n³). Skip duplicate anchors to avoid duplicate triplets.
Q — Two pointers vs hash table: when to pick which?
| Aspect | Two Pointers | Hash Map |
|---|---|---|
| Requires sorted input | Yes (or sort it) | No |
| Extra space | O(1) | O(n) |
| Time | O(n) after sort | O(n) |
| In-place mutations | Yes | No |
Rule of thumb: if the input is already sorted or the constraint is "O(1) space", use two pointers. If unsorted and space is fine, hash map is simpler.
Bug — Off-by-one when skipping duplicates
| 1 | // After finding a match in 3Sum, skip duplicates: |
| 2 | while (left < right && arr[left] === arr[left + 1]) left++; |
| 3 | while (left < right && arr[right] === arr[right - 1]) right--; |
| 4 | left++; |
| 5 | right--; |
| 6 | // BUG: if you forget the left < right guard, you can |
| 7 | // overshoot and read out of bounds or miss a triplet. |
Classic interview question (Two Sum on sorted array)
| 1 | function twoSum(numbers: number[], target: number): [number, number] { |
| 2 | let left = 0, right = numbers.length - 1; |
| 3 | while (left < right) { |
| 4 | const sum = numbers[left] + numbers[right]; |
| 5 | if (sum === target) return [left + 1, right + 1]; // 1-indexed |
| 6 | if (sum < target) left++; |
| 7 | else right--; |
| 8 | } |
| 9 | return [-1, -1]; // no solution (won't happen per problem guarantee) |
| 10 | } |
| 11 | // Time: O(n) · Space: O(1) |
The Deep Dive
— Spec refs, engine internals, the minutiae.Two flavors of two pointers
Left / Right (squeeze)
- Start at opposite ends, move inward
- Requires sorted (or symmetric) input
- Uses: Two Sum, 3Sum, palindrome, trapping rain
- O(n) time, O(1) space
Slow / Fast (runner)
- Both start at the same end; fast races ahead
- Works on unsorted arrays and linked lists
- Uses: remove duplicates, Floyd's cycle detection
- O(n) time, O(1) space
Floyd's cycle detection (slow/fast on linked list)
The classic linked-list cycle problem: is there a loop? Slow pointer moves one step, fast pointer moves two. If they ever point to the same node, there's a cycle. If fast hits null, the list is acyclic.
| 1 | function hasCycle(head: ListNode | null): boolean { |
| 2 | let slow = head, fast = head; |
| 3 | while (fast !== null && fast.next !== null) { |
| 4 | slow = slow!.next; |
| 5 | fast = fast.next.next; |
| 6 | if (slow === fast) return true; |
| 7 | } |
| 8 | return false; |
| 9 | } |
| 10 | // The "meeting point" can also pinpoint the cycle start — |
| 11 | // reset one pointer to head, advance both by 1 until they meet. |
Why it works: the fast pointer laps the slow one inside the cycle. The gap closes by 1 each iteration → they must meet in O(n).
Multiple pointers (3+ pointers)
Some problems generalise naturally: "4Sum" runs two-pointer inside a double outer loop (O(n³)). "Dutch National Flag" (sort array of 0s, 1s, 2s) uses three pointers — low, mid, high — partitioning in a single pass.
| 1 | // Dutch National Flag — O(n), O(1) |
| 2 | function sortColors(nums: number[]): void { |
| 3 | let low = 0, mid = 0, high = nums.length - 1; |
| 4 | while (mid <= high) { |
| 5 | if (nums[mid] === 0) { |
| 6 | [nums[low], nums[mid]] = [nums[mid], nums[low]]; |
| 7 | low++; mid++; |
| 8 | } else if (nums[mid] === 1) { |
| 9 | mid++; |
| 10 | } else { // 2 |
| 11 | [nums[mid], nums[high]] = [nums[high], nums[mid]]; |
| 12 | high--; // don't increment mid — the swapped element is unexamined |
| 13 | } |
| 14 | } |
| 15 | } |
Complexity comparison across variants
| Problem | Variant | Time | Space |
|---|---|---|---|
| Two Sum (sorted) | Left/Right | O(n) | O(1) |
| 3Sum | Left/Right × loop | O(n²) | O(1)* |
| Remove Duplicates | Slow/Fast | O(n) | O(1) |
| Trapping Rain Water | Left/Right | O(n) | O(1) |
| Cycle Detection | Slow/Fast | O(n) | O(1) |
* O(log n) or O(n) if you count the sorting step for 3Sum
Related patterns
- Sliding Window — sibling pattern; left/right on unsorted arrays, constraint-driven instead of sum-driven
- Binary Search — also exploits sorted order but O(log n) per query, not O(n) end-to-end
- Monotonic Stack — for "next greater element" style problems where two-pointer would need a sorted invariant it can't guarantee
- Prefix Sums — when you need arbitrary range sums, not just a moving window
Interview Questions
— Real questions from real interviews — with answers.Array must be sorted (or have a monotonic property) so moving a pointer predictably changes the sum/product.
Two pointers is O(1) space but requires a sorted array; hashmap is O(n) space but works unsorted.
Skip duplicate values for the outer loop and for both inner pointers after a match.
Slow pointer moves 1 step, fast moves 2 — if a cycle exists they must eventually land on the same node.
Track left-max and right-max as you converge inward — water at each bar is min(leftMax, rightMax) - height[i].
Memory Game
— Quick quiz — lock the concept in long-term memory.What is the time complexity of 3Sum using sorting + two-pointer?