Two Pointer Technique

The Core Idea

The two pointer technique is the simplest, most repeatedly useful trick for collapsing apparently-quadratic array problems to linear time. The idea is unreasonably small. Maintain two indices, call them $i$ and $j$, walking over the array. At every step, compare the values at those indices, infer something about the answer's location, and advance whichever pointer the comparison tells you to. Each pointer moves only forward (or only inward). Each crosses the array at most once. Total work: $O(n)$.

Why does this beat the brute force? A brute force would consider every pair $(i, j)$ — that is $\binom{n}{2} = \Theta(n^2)$ pairs. The two-pointer trick exploits a monotone structure (often sortedness, sometimes a geometric envelope) to eliminate entire columns or rows of the pair matrix in a single move. We will see the precise elimination argument three times — for Two-Sum, for Container with Most Water, and for 3-Sum. Once you see the shape, you will recognize it the rest of your life.

Slogan: two pointers turn an $O(n^2)$ search over pairs into an $O(n)$ march, by pruning at least one candidate from the remaining search space at every comparison.

The Three Flavors

Two-pointer code in the wild comes in three distinct shapes. The differences look cosmetic but the invariants and proofs differ.

Visual schematic

Converging pointers shrink a window from the outside in. Fast/slow pointers grow a kept-prefix from the inside out. Merge pointers ride two parallel rails. The asymptotic complexity is the same — the invariant we prove is what differs.

Why It Works: The Invariant

Two-pointer code is short. It is also easy to get wrong. The discipline that protects you is the same one that protects binary search and induction: state the invariant, then prove every move preserves it.

The universal converging-pointer invariant

For Two-Sum on a sorted array the proof of the invariant is a two-line case split:

1. Case $A[\mathit{lo}] + A[\mathit{hi}] < T$. For every $k \le \mathit{hi}$, the pair $(\mathit{lo}, k)$ has sum $A[\mathit{lo}] + A[k] \le A[\mathit{lo}] + A[\mathit{hi}] < T$ (because the array is sorted ascending so $A[k] \le A[\mathit{hi}]$). So index $\mathit{lo}$ can never participate in a valid pair within this window. We may eliminate $\mathit{lo}$ and the invariant is preserved.
2. Case $A[\mathit{lo}] + A[\mathit{hi}] > T$. Symmetric: $\mathit{hi}$ can never participate, so we eliminate $\mathit{hi}$.
3. Case equality. Found.

Each step permanently removes a row or a column from the implicit pair matrix. Out of $n^2$ pairs we end up examining only $O(n)$, because each pointer-move retires $\Theta(\text{remaining window})$ pairs in one shot. That is the algorithm in one sentence.

Worked Problem 1: Two-Sum on a Sorted Array

Problem. Given a sorted ascending array $A$ of length $n$ and a target $T$, return indices i &lt; j with $A[i] + A[j] = T$, or report none.

Three solutions, three complexities

The two-pointer version costs no extra memory and has the smallest constant factor — a single addition and one comparison per step. On a sorted input there is essentially no reason to use anything else.

Trace

$A = [1, 3, 4, 6, 8, 9, 11, 14]$, $T = 13$:

Five iterations on a length-eight array. Brute force would have considered $\binom{8}{2} = 28$ pairs.

Worked Problem 2: Reverse In Place

The textbook two-pointer task: $\mathit{lo} = 0$, $\mathit{hi} = n - 1$; swap $A[\mathit{lo}]$ with $A[\mathit{hi}]$; converge.

1def reverse_in_place(A):
2    lo, hi = 0, len(A) - 1
3    while lo < hi:
4        A[lo], A[hi] = A[hi], A[lo]
5        lo += 1
6        hi -= 1

Exactly $\lfloor n / 2 \rfloor$ swaps, $O(n)$ time, $O(1)$ extra space. The middle element of an odd-length array does not move — the loop simply exits when $\mathit{lo} = \mathit{hi}$.

This three-line routine is also the building block for rotate-by-k via the three-reverses trick we saw in §5.4.

Worked Problem 3: Remove Duplicates from a Sorted Array

Problem (LeetCode 26). Given a sorted array, compact it in place so that the unique values occupy a prefix $A[0 \ldots k - 1]$. Return $k$. The remaining cells are scratch; the caller will not read them.

This is the canonical fast / slow shape:

• slow points at the next free position in the kept prefix — i.e. $A[0 \ldots \mathit{slow}]$ is duplicate-free.
• fast scans the unprocessed tail. Whenever it sees a new value, copy it into $A[\mathit{slow} + 1]$ and advance $\mathit{slow}$.

Trace on a small example

$A = [1, 1, 2, 2, 3, 4, 4]$:

Final length: $k = \mathit{slow} + 1 = 4$. Both pointers traversed the array exactly once; $O(n)$ reads, at most $O(n)$ writes, no allocation. Compare against the "copy unique elements into a new list" approach: same time, but $O(n)$ extra memory and worse cache behavior.

Worked Problem 4: Container with Most Water

Problem (LeetCode 11). Given an array $H$ of non-negative heights, choose two indices i &lt; j to maximize the rectangular water area:

$\text{area}(i, j) \;=\; (j - i) \cdot \min(H[i], H[j]).$

The brute force is $O(n^2)$. The two-pointer algorithm is $O(n)$. The core decision: always move the pointer at the SHORTER wall.

Why moving the shorter wall is correct: an exchange argument

Suppose H[\mathit{lo}] &lt; H[\mathit{hi}] (the symmetric case is identical). The current candidate area is $(\mathit{hi} - \mathit{lo}) \cdot H[\mathit{lo}]$. Consider any pair $(\mathit{lo}, k)$ with \mathit{lo} &lt; k &lt; \mathit{hi}:

1. The width strictly decreases: (k - \mathit{lo}) &lt; (\mathit{hi} - \mathit{lo}).
2. The min height is at most $H[\mathit{lo}]$ (it cannot exceed either wall).

So $\text{area}(\mathit{lo}, k) \le (\mathit{hi} - \mathit{lo}) \cdot H[\mathit{lo}]$ — every pair involving the shorter wall and any k &lt; \mathit{hi} is bounded by the current area. Therefore index $\mathit{lo}$ is provably exhausted; advancing it loses no candidate. Conversely, advancing $\mathit{hi}$ when it is the taller wall would discard the pair $(\mathit{lo}, \mathit{hi})$ without justification — we might be skipping an optimum.

Worked Problem 5: 3-Sum

Problem (LeetCode 15). Given an array $A$, return every triple of distinct indices i &lt; j &lt; k with $A[i] + A[j] + A[k] = 0$. Triples must be unique by value.

The brute force is $O(n^3)$. The standard improvement: sort, then for each pivot $i$ run two-pointer on the suffix $A[i + 1 \ldots n - 1]$, looking for the pair that sums to $-A[i]$. Sorting costs $O(n \log n)$. The pivot loop runs $n$ times; each pivot costs $O(n)$ work — total $O(n^2)$.

1def three_sum(A):
2    A = sorted(A)
3    n = len(A)
4    out = []
5    for i in range(n - 2):
6        if i > 0 and A[i] == A[i - 1]:
7            continue                       # skip duplicate pivots
8        lo, hi = i + 1, n - 1
9        target = -A[i]
10        while lo < hi:
11            s = A[lo] + A[hi]
12            if s == target:
13                out.append((A[i], A[lo], A[hi]))
14                lo += 1
15                hi -= 1
16                while lo < hi and A[lo] == A[lo - 1]:
17                    lo += 1                # skip duplicate lo
18                while lo < hi and A[hi] == A[hi + 1]:
19                    hi -= 1                # skip duplicate hi
20            elif s < target:
21                lo += 1
22            else:
23                hi -= 1
24    return out

The two duplicate-skip lines are the easiest place to introduce bugs. The standard pitfall is to skip duplicates only on one side, or before checking the equality case, leading to missed or repeated triples. The pattern above skips after the equality move, which is the only correct order.

3-Sum is the prototype: any "k-Sum" problem reduces to $O(n^{k-1})$ by sorting once and recursively fixing pivots, with two-pointer at the bottom. 4-Sum is $O(n^3)$; 5-Sum is $O(n^4)$; etc.

Worked Problem 6: Trapping Rain Water

Problem (LeetCode 42). Heights $H[0 \ldots n - 1]$ represent an elevation map, each bar of unit width. After it rains, how much water is trapped above the bars?

The water above index $i$ is

$\mathrm{water}(i) \;=\; \min\bigl(\mathrm{maxL}(i),\, \mathrm{maxR}(i)\bigr) - H[i],$

where $\mathrm{maxL}(i)$ / $\mathrm{maxR}(i)$ are the tallest bars at or to the left / right of $i$. The naive solution precomputes both arrays — $O(n)$ time but $O(n)$ extra space.

The two-pointer beauty: maintain running maxima $\mathit{leftMax}$ and $\mathit{rightMax}$ on the fly, and process whichever side has the smaller running max. Reasoning: at index $\mathit{lo}$, if $\mathit{leftMax} \le \mathit{rightMax}$ then the bar to the right is at least as tall as anything we have seen on the left — the water height at $\mathit{lo}$ is fully determined by the left side. Compute $\mathit{leftMax} - H[\mathit{lo}]$ and advance $\mathit{lo}$.

1def trap(H):
2    lo, hi = 0, len(H) - 1
3    left_max = right_max = 0
4    water = 0
5    while lo < hi:
6        if H[lo] < H[hi]:
7            left_max = max(left_max, H[lo])
8            water += left_max - H[lo]
9            lo += 1
10        else:
11            right_max = max(right_max, H[hi])
12            water += right_max - H[hi]
13            hi -= 1
14    return water

$O(n)$ time, $O(1)$ space. Eliminates the need for the maxL / maxR arrays. The same invariant — "the side with the smaller running max is decided" — drives the entire computation.

Worked Problem 7: Dutch National Flag

Problem (Dijkstra, 1976). Given an array of values in $\{0, 1, 2\}$, sort it in a single linear pass with constant extra space. Equivalently: 3-way partition around a pivot.

Three pointers, not two: $\mathit{lo}$, $\mathit{mid}$, $\mathit{hi}$. Invariant:

• $A[0 \ldots \mathit{lo} - 1]$ are all 0 (the "reds").
• $A[\mathit{lo} \ldots \mathit{mid} - 1]$ are all 1 (the "whites").
• $A[\mathit{mid} \ldots \mathit{hi}]$ is the unprocessed region.
• $A[\mathit{hi} + 1 \ldots n - 1]$ are all 2 (the "blues").

1def dutch_flag(A):
2    lo, mid, hi = 0, 0, len(A) - 1
3    while mid <= hi:
4        if A[mid] == 0:
5            A[lo], A[mid] = A[mid], A[lo]
6            lo += 1
7            mid += 1
8        elif A[mid] == 1:
9            mid += 1
10        else:                              # A[mid] == 2
11            A[mid], A[hi] = A[hi], A[mid]
12            hi -= 1                        # do NOT advance mid here

The asymmetry on the last branch is the single most-confused detail: when we swap a 2 from the back to $\mathit{mid}$, the value we pulled in is unprocessed and might be 0, 1, or 2 — so $\mathit{mid}$ stays put for re-examination on the next iteration. When we swap a 0 forward, the value pulled in from $\mathit{lo}$ can only be a 1 (by the invariant), so we are safe to advance $\mathit{mid}$.

Quicksort's 3-way partition is exactly this routine, generalized from the constants 0/1/2 to less-than / equal / greater-than the pivot. It is the algorithmic heart of every fast sorting library (libstdc++, V8 TimSort fallback, Rust's pdqsort).

Interactive: Two-Pointer Lab

Pick a problem, edit the array, drag the target slider for Two-Sum, and step through the algorithm. The blue arrow is $\mathit{lo}$ / $\mathit{slow}$; the red arrow is $\mathit{hi}$ / $\mathit{fast}$. The decision panel narrates the comparison being made; the running answer updates in green. For Container with Most Water, the cells are drawn as bars so you can see which wall is the binding constraint — and confirm visually that we always move the shorter one.

Reference Implementations: Python and TypeScript

Below are clean, production-quality versions of the three workhorse routines in two languages. Every meaningful line is annotated with the invariant it preserves and the cost it incurs. Read these side-by-side: the algorithms are identical, only the syntax differs — which is itself a useful lesson about how language-agnostic the two-pointer pattern is.

A = [1,3,4,6,8,9,11,14], T=13  →  lo=0 (val 1), hi=7 (val 14)

Iteration 1: lo=0, hi=7  →  s = 1+14 = 15

s = 1+14 = 15 > 13 doesn't apply; s = 1+11 = 12 < 13 → lo++

1+14=15 > 13 → hi--

A = [1,1,2,2,3,4,4]  →  start slow=0 (value 1)

fast=2: A[2]=2 ≠ A[0]=1 → unique

After fast=2: slow=1, A=[1,2,2,2,3,4,4]

H = [1,8,6,2,5,4,8,3,7]  →  lo=0 (h=1), hi=8 (h=7)

lo=0,hi=8: area=(8−0)·min(1,7)=8·1=8

H[0]=1 < H[8]=7 → lo++ (eliminate lo=0 forever)

1def two_sum_sorted(A, T):
2    """Find indices i < j with A[i] + A[j] == T. A must be sorted ascending."""
3    lo, hi = 0, len(A) - 1
4    while lo < hi:
5        s = A[lo] + A[hi]
6        if s == T:
7            return (lo, hi)
8        elif s < T:
9            lo += 1
10        else:
11            hi -= 1
12    return None
13
14
15def remove_duplicates(A):
16    """Compact a sorted list in place. Returns the new logical length k.
17    A[0..k-1] holds the unique values; A[k..] is unspecified scratch."""
18    if not A:
19        return 0
20    slow = 0
21    for fast in range(1, len(A)):
22        if A[fast] != A[slow]:
23            slow += 1
24            A[slow] = A[fast]
25    return slow + 1
26
27
28def container_with_most_water(H):
29    """Pick i < j maximizing (j - i) * min(H[i], H[j]). H is heights, any order."""
30    lo, hi = 0, len(H) - 1
31    best = 0
32    while lo < hi:
33        area = (hi - lo) * min(H[lo], H[hi])
34        if area > best:
35            best = area
36        # Move the SHORTER side; moving the taller cannot improve on this width.
37        if H[lo] < H[hi]:
38            lo += 1
39        else:
40            hi -= 1
41    return best

1function twoSumSorted(A: number[], T: number): [number, number] | null {
2  let lo = 0;
3  let hi = A.length - 1;
4  while (lo < hi) {
5    const s = A[lo] + A[hi];
6    if (s === T) return [lo, hi];
7    if (s < T) lo++;
8    else hi--;
9  }
10  return null;
11}
12
13function removeDuplicates(A: number[]): number {
14  if (A.length === 0) return 0;
15  let slow = 0;
16  for (let fast = 1; fast < A.length; fast++) {
17    if (A[fast] !== A[slow]) {
18      slow++;
19      A[slow] = A[fast];
20    }
21  }
22  return slow + 1;
23}
24
25function containerWithMostWater(H: number[]): number {
26  let lo = 0;
27  let hi = H.length - 1;
28  let best = 0;
29  while (lo < hi) {
30    const area = (hi - lo) * Math.min(H[lo], H[hi]);
31    if (area > best) best = area;
32    if (H[lo] < H[hi]) lo++;
33    else hi--;
34  }
35  return best;
36}

Real-World Patterns

1. Merge step of merge sort. Two pointers, one per input run, advance whichever value is smaller. Output is sorted. The single most-implemented two-pointer routine in computing history — every external sort in every database depends on it.
2. Database joins on sorted indexes. When two tables are pre-sorted on the join key, a sort-merge join reduces to two pointers walking in lockstep — $O(n + m)$ total, with no hash-table memory. PostgreSQL, ClickHouse, and most columnar engines pick sort-merge over hash-join for very large inputs precisely because of this.
3. Memory compaction in garbage collectors. A copying / mark-compact GC uses a slow / fast pair to slide live objects down over the dead ones — exactly the remove-duplicates pattern generalized to typed heap blocks.
4. Network packet windows. Sliding-window receivers (TCP, QUIC) maintain head and tail pointers into a ring of recently-seen packets. Acknowledgements advance the head; arrivals advance the tail.
5. DNA / RNA read alignment. Anchor extension algorithms (BWA-MEM, minimap2) seed an alignment then walk two pointers outward over the read and the reference, scoring matches and gaps.
6. Audio DSP — sliding window of samples. Running mean / running max / FIR filter all maintain a head and tail into a circular buffer of recent samples.
7. Best buy / best sell single-pass. Walk the price series with two pointers — left tracks the running min so far, right is the current day. Maximum profit in $O(n)$.
8. Diff and merge of sorted log files. Pipe two sorted streams; advance whichever has the older timestamp; emit merged output. Used by every distributed log aggregator.
9. Filter-and-pack in column databases. Apply a predicate over a column; use a slow pointer to write the surviving rows back into the same column, in place — removes a full pass and an extra column allocation.
10. Edit-distance ladder for autocorrect. When two candidate words share a long common prefix and suffix, two pointers identify the differing core in linear time, which is then fed to a smaller dynamic-programming table.

Pattern Recognition Checklist

When a problem walks in, ask these four questions. If you answer "yes" to all four, two-pointer is almost certainly the right tool.

1. Is the input an array or a sequence? Two-pointer fundamentally relies on indexable, bounded structure.
2. Are you searching for a pair, a window, or a compacted subsequence? If the answer is a pair $(i, j)$ or a contiguous run, two-pointer has a chance. If the answer is a set or a complex subset, it probably does not.
3. Is the brute force $O(n^2)$ or worse? Otherwise you do not need the trick.
4. Is there a monotone property that lets you discard at least one candidate per comparison? Sortedness is the most common; geometric envelopes (Container, Trapping Water) and duplicate-adjacency (LeetCode 26) are the others. If you cannot articulate the monotone property, you cannot prove the algorithm correct, so you should not write it.

Pitfalls

1. Off-by-one at the boundary. The converging-pointer loop is while lo < hi, not while lo <= hi. The two are different in palindrome checks, in container-with-most-water, and in 3-Sum (where lo == hi would mean choosing the same index twice).
2. Forgetting to skip duplicates in 3-Sum. Either skip both $\mathit{lo}$ AND $\mathit{hi}$ after a hit, or neither — the one-sided skip produces missed or duplicated triples. And always skip after the equality move, not before.
3. Advancing both pointers on a Dutch-flag swap-with-hi. When you swap $A[\mathit{mid}]$ with $A[\mathit{hi}]$, the value pulled in is unverified. Decrementing $\mathit{hi}$ is correct; advancing $\mathit{mid}$ would skip an unprocessed element.
4. Mutating while iterating from both ends. If you remove or insert in the middle of the array while two pointers are live, the indices invalidate. Either mutate only at the endpoints (push / pop) or post-process after both pointers terminate.
5. Wrong shift direction in fast / slow compaction. Always copy $A[\mathit{fast}]$ into $A[\mathit{slow}]$, never the reverse. fast leads, slow follows.
6. Confusing "sorted by value" with "sorted by original index". Two-Sum-with-indices returns original positions; if you sort the array in place, you destroy the index mapping. Either sort a list of (value, index) pairs, or use the hash-map$O(n)$ variant.
7. Assuming the input is sorted when it is not. The most common silent bug. Every two-pointer routine that requires sorting should either assert it or sort defensively at entry. The$O(n \log n)$ sort cost still beats the $O(n^2)$ brute force for any n &gt; 30 in practice.

The next section, Sliding Window, is two-pointer's sibling: same fast / slow shape, but the question changes from "find a pair" to "find a contiguous subarray with property $P$." Once you have the two patterns in muscle memory, an enormous fraction of array problems become routine.