Two pointers — collapse O(n²) to O(n)
📖 Walk me through it — plain English
Two pointers means we keep two index variables (call them i and j) that point at two positions in an array, and we walk them toward each other so we scan the whole array in a single pass. An index is just a position number: in a list, position 0 is the first item, position 1 the second, and so on. The trick lets us replace a slow "compare every pair against every other pair" approach — which is O(n²), meaning the work grows like the array length squared — with a fast O(n) single sweep, where the work grows just in step with the length.
This lesson's example is Container With Most Water. Picture a row of vertical walls of different heights. Pick any two walls; together with the flat ground they form a bucket. The water it holds is its area = the horizontal distance between the two walls (their width) times the height of the shorter wall (water spills over the short side, so the short wall is the limit). We want the two walls that hold the most water.
Analogy: imagine two people holding the ends of a sagging towel to catch rain. The towel can only fill as high as whoever is holding it lower — so the short holder caps how much you collect. To do better you tell the shorter holder to step inward and try a new spot, because keeping the short one fixed can never help. That is exactly the rule in the code: start one pointer at each end, and each round move the pointer on the shorter side inward. (In the code, if h[i] < h[j] we step i forward; otherwise we step j back — so we always advance whichever wall is the shorter one, with ties moving j.)
Let's trace it on the tiny array h = [1, 5, 4, 3]. We start with i at the far left and j at the far right, and a running best = 0. Highlighted cells are where the two pointers sit; faded struck-through cells are positions a pointer has already moved past.
Why moving the shorter wall is safe: the area is capped by the shorter wall. If we instead moved the taller wall inward, the width shrinks AND the height is still capped by that same short wall, so the area can only get worse — we'd be throwing away a chance to improve for no reason. Moving the short wall is the only move that could find something taller and beat our record. Because each round we advance exactly one pointer and they only ever move toward each other, after at most n steps they meet — that single sweep is why it's O(n) time, and we keep just a couple of variables so it's O(1) extra space.
Sorted input + pair/triple/range = two pointers. Two indices walking inward (or together) cover the search space once.
The one idea, stated plainly
A pointer here is just a variable that holds an index — a position number into an array. "Two pointers" is the habit of keeping two such position variables and moving them according to a rule, so that together they sweep the data in one pass instead of nesting two loops. The naive way to examine all pairs in an array is a loop inside a loop: for each i, try every j — that is O(n²) (roughly n×n comparisons). The two-pointer move replaces that double loop with a single coordinated walk: each step you advance one of the two pointers and never revisit a position, so the total work is proportional to the array length — O(n) — using only a handful of index variables, which is O(1) extra space (no new arrays, no hash map).
The catch is that you can only skip work this way when there is structure you can exploit. The most common structure is a sorted array (every element is no larger than the one to its right). When the data is sorted, you can look at the current pair, decide with certainty which direction to move, and safely throw away a whole range of possibilities you will never need to check. Without that ordering, moving a pointer "the wrong way" might skip the very answer you were looking for — so for many variants the sorted-array precondition is what makes the trick correct, not just fast.
The three flavors — and the vocabulary
Almost every two-pointer problem is one of three shapes. Learn the names so you can recognise which one a problem wants:
One pointer starts at the left end, the other at the right end, and they walk toward each other until they meet or cross. Each step you compare the two ends and move one of them inward. Used for: pair-sum in a sorted array, reversing in place, palindrome checks, Container With Most Water. This is the flavor in the walkthrough above.
Both pointers start near the same end and move the same way, but at different speeds or for different jobs. A slow pointer marks "where the next kept element goes"; a fast pointer scans ahead reading every element. Used for: remove duplicates, move zeros, and (in linked lists) cycle detection where fast moves 2 nodes per slow's 1.
One pointer per array, each advancing through its own list. Used for merging two sorted arrays, finding the intersection of two sorted lists, or comparing two sequences. You advance whichever pointer points at the smaller (or matching) element.
- In-place: mutating the input array directly, reusing its own memory, instead of building a new array — that's how you stay at O(1) extra space.
- Partition: rearranging elements so everything of one kind sits before everything of another (e.g. all kept items before all discarded items), which is exactly what the slow pointer's position records.
- Sorted array + pair search
- Reverse / palindrome
- Two arrays merging
- In-place mutation
- Opposite ends moving in
- Same direction (fast/slow)
- Three pointers (3-Sum)
Traced example A — opposite-ends: pair-sum in a sorted array
Goal: given a sorted array and a target, find two values that add up to the target. This is where the sorted precondition earns its keep. Put i at the left, j at the right, and look at nums[i] + nums[j]. Because the array is sorted, the leftmost value is the smallest and the rightmost is the largest, so the current sum is somewhere in the middle of what's possible. The rule: if the sum is too small, the only way to grow it is to move i right (toward larger values); if it's too big, move j left (toward smaller values); if it's exactly the target, you're done.
Trace on nums = [2, 5, 8, 11], target = 13. The brackets show where i and j sit each round.
# target = 13
# [2] 5 8 [11] sum = 2 + 11 = 13 == target -> FOUND (i=0, j=3)Found on the first comparison here. To see the steering, trace target = 10 on the same array:
# target = 10
# [2] 5 8 [11] sum = 2 + 11 = 13 > 10 too big -> move j left
# [2] 5 [8] 11 sum = 2 + 8 = 10 == 10 -> FOUND (i=0, j=2)When the sum was 13 (too big), moving j left was safe because every pair using nums[j]=11 with an even smaller i would only be smaller still in width yet still over target — and pairing 11 with anything to the right of i would be even larger. So discarding the 11 column entirely loses no valid answer. That is the sorted guarantee in action: one comparison eliminates a whole row or column of the pair grid.
def pair_sum(nums, target):
i, j = 0, len(nums) - 1
while i < j:
s = nums[i] + nums[j]
if s == target: return (i, j) # found a pair
if s < target: i += 1 # too small -> grow it
else: j -= 1 # too big -> shrink it
return None # pointers crossed, no pairTraced example B — same-direction: remove duplicates in place
Goal: given a sorted array, squeeze out duplicates so each value appears once, in place, and report the new length. Here the two pointers move the same direction. The slow pointer w (for "write") marks the last position we've finalized — everything at index ≤ w is the deduped result so far. The fast pointer r (for "read") scans every element looking for the next value that differs from what's already written. When it finds a new value, we advance w and copy the value into that slot. The region behind w is the partition of kept elements.
Trace on nums = [1, 1, 2, 3, 3]. w starts at 0 (the first element is trivially kept); r scans from 1. The ^w / ^r markers show pointer positions:
# idx: 0 1 2 3 4
# [ 1 1 2 3 3 ]
# r=1: nums[1]=1 == nums[w]=1 (dup) -> skip, w stays 0
# r=2: nums[2]=2 != nums[w]=1 (new) -> w=1, copy 2 -> [1 2 2 3 3]
# r=3: nums[3]=3 != nums[w]=2 (new) -> w=2, copy 3 -> [1 2 3 3 3]
# r=4: nums[4]=3 == nums[w]=3 (dup) -> skip, w stays 2
# done: kept length = w + 1 = 3, result prefix = [1, 2, 3]The fast pointer touched every element exactly once and the slow pointer only moved forward, so this is a single O(n) sweep with no extra array — O(1) space. "Move zeros to the end" is the same shape: slow points at where the next non-zero goes, fast scans for non-zeros, and you swap them forward.
def dedupe(nums):
if not nums: return 0
w = 0 # slow: last finalized index
for r in range(1, len(nums)): # fast: scans every element
if nums[r] != nums[w]: # found a new value
w += 1
nums[w] = nums[r] # write it just past the kept region
return w + 1 # new length of the deduped prefixWhy it's O(n) time and O(1) space
In every flavor, each pointer only ever moves in one direction and never backtracks. In the converging flavor the two indices start n apart and close in by at least one each round, so the loop runs at most n times. In the same-direction flavor the fast pointer visits each index once. Either way the total number of steps is bounded by the array length, giving O(n) time — a clean win over the O(n²) nested-loop brute force. And because we only store a few integer indices (and mutate the array in place when the problem allows), we add no memory that grows with the input: O(1) extra space.
Recognition signals and pitfalls
- The input is (or can be) sorted and you want a pair/triple meeting a sum or range condition.
- You must work in place with O(1) extra space (reverse, dedupe, move/partition elements).
- You're merging or comparing two sorted sequences.
- It's a palindrome check or a "from both ends" symmetric scan.
- A brute-force solution is an obvious O(n²) double loop over pairs.
- Forgetting the array must be sorted. The pair-sum "move left or right" decision is only valid on sorted data — on unsorted input you can't decide which pointer to move, so sort first (or use a hash set instead).
- Off-by-one in the loop condition. Use
while i < jfor converging pairs (you need two distinct indices); usei <= jonly if the middle element should also be processed. - Moving both pointers when you should move one. In converging problems, advance exactly one pointer per round based on the comparison.
- Skipping duplicates in 3-Sum. When triples must be unique, advance past equal neighbors after recording a hit, or you'll emit the same triple twice.
Mental check before you commit: "Can I look at my current two positions and decide, with certainty, which one to move without ever needing to come back?" If yes, two pointers works. If the answer depends on data you'd have to re-scan, you probably need a hash map or a different pattern instead.
def max_area(h):
i, j = 0, len(h) - 1
best = 0
while i < j:
best = max(best, (j - i) * min(h[i], h[j]))
if h[i] < h[j]: i += 1 # move the shorter side
else: j -= 1
return bestfunction maxArea(h: number[]): number {
let i=0, j=h.length-1, best=0;
while (i < j) {
best = Math.max(best, (j - i) * Math.min(h[i], h[j]));
h[i] < h[j] ? i++ : j--;
}
return best;
}Your turn — reverse an array in place with the two-pointer swap. Runs in your browser against live tests:
Go deeper (optional): the same "scan from both ends, decide one move" idea generalizes to 3-Sum (fix one element, two-pointer the rest of the sorted array) and to trapping rain water (converging pointers tracking the tallest wall seen from each side). If you want outside reading, LeetCode's "Two Pointers" tag and the classic problems "Container With Most Water," "3Sum," and "Trapping Rain Water" are the canonical drills.