Coding Prep
Two Pointers
Two index variables that eliminate the inner loop - the opposite-ends pattern for sorted-array pair problems and the same-direction pattern for partitioning and in-place removal.
What is two pointers?
Two pointers is an algorithmic technique that uses two index variables to scan an array, eliminating the need for a nested loop. Instead of O(n²), most problems reduce to O(n).
The key insight: if you are searching for a pair satisfying some condition in a sorted array, you can start one pointer at each end. If the current pair's value is too small, move the left pointer right (increasing the sum); if too large, move the right pointer left (decreasing it). Each step eliminates one pointer position from consideration - you have seen everything that pointer could pair with, given the current state of the other pointer.
Two pointers appears in two main configurations. The opposite-ends (converging) variant starts left at index 0 and right at the last index and moves them toward each other. The same-direction variant has both pointers start near the left and move forward, but at different speeds or with different advancement conditions - used for in-place element removal and partitioning.
Two pointers is not the same as binary search. Binary search halves the space at each step without examining every element. Two pointers examines every element in a structured sweep - it trades the logarithmic property for the ability to maintain a running relationship between two positions.
Core operations
| Variant | Direction | Initial setup | When to advance |
|---|---|---|---|
| Opposite ends | Converging | left=0, right=n-1 | Move based on comparison to target condition |
| Same direction (removal) | Both forward | slow=0, fast=0 | fast always; slow only when element qualifies |
| Same direction (partition) | Both from ends | left=0, right=n-1 | Swap and advance both when misplaced element found |
Key patterns
Opposite-ends (sorted array pair sum)
Start one pointer at the left (smallest value) and one at the right (largest value), then move whichever one pushes the running sum toward the target.
When to use - the array is sorted (or you can afford to sort it) and you need a pair or triplet meeting a sum condition: a target sum, the widest container, a palindrome check. A brute-force double loop tries every pair at O(n²); sortedness lets one comparison decide which pointer to move and collapses it to O(n).
How it works - the loop runs while left < right, never <=, because a valid pair never reuses one element. Each step moves exactly one pointer inward and the two only ever travel toward each other, so together they take at most n steps total - that is why it is O(n) and neither pointer backtracks. The comparison is valid only because the array is sorted: moving left rightward can only grow the sum and moving right leftward can only shrink it, so each move provably eliminates one pointer position from consideration.
Same-direction (in-place removal)
Both pointers start near the front and move forward, with slow marking where the next kept element goes and fast scanning every element.
When to use - you must remove or deduplicate elements in place, with no second array. The signal is "modify the array in-place" or "return the new length". Building a fresh filtered array would cost O(n) extra space; the slow/fast sweep does it in O(1).
How it works - fast reads every element once. When fast lands on a qualifying element, write it to slow's position and then advance slow. The invariant is that everything before slow is already the compacted result, so slow is always the next free write slot. Because each pointer moves forward only and fast makes a single pass, the whole thing is O(n) time and O(1) space; the count of kept elements is slow + 1, not slow.
slow tracks the last valid write position, not the count - the count is slow + 1. Advance slow before writing to avoid overwriting the current valid element with itself.Canonical examples
Container with most water
The opposite-ends pointer starts with the widest possible window. The area is limited by the shorter of the two sides. Moving the taller side inward can only reduce width without any possibility of increasing the height constraint, so the area can only shrink. Moving the shorter side inward is the only move that could find a better pair - and it is safe because every pair involving the current shorter side at a wider width has already been covered.
Three sum
Reduce 3Sum to a 2Sum with two pointers. Sort first, then fix one element with an outer loop and apply opposite-ends two pointers on the subarray to the right. Deduplication requires skipping repeated values for the fixed element and for both inner pointers after recording a match.
When to reach for two pointers
- The array is sorted and you need to find a pair or triplet satisfying a sum condition.
- You need to remove or deduplicate elements in-place without allocating extra space.
- The problem asks you to check if a string or array is a palindrome - compare from both ends converging inward.
- You need to partition an array in-place (Dutch flag, separate negatives and positives).
- A brute-force nested loop is O(n²) and the array is sorted - ask whether moving two pointers eliminates the inner loop.
- The problem involves area maximization or water trapping with height boundaries at two positions.
Practice problems
- Two Sum II - Input Array Is Sorted - Opposite ends; the canonical two-pointer template.
- Valid Palindrome - Converging pointers with character normalization.
- Container With Most Water - Area maximization with the move-shorter-side insight.
- 3Sum - Sort + fix one + two pointers; deduplication required.
- Remove Duplicates from Sorted Array - Same-direction slow/fast in-place removal.
- Trapping Rain Water - Two pointers tracking running max from each side; the hardest two-pointer problem.
Done reading? Mark it so it sticks in your dashboard.