Two Pointers: The Core Idea

Two pointers is the pattern where you keep two indices into a sequence and move them under a rule, so that each move rules out a whole group of candidates instead of one. It is usually the first optimisation interviewers expect you to find, because the brute force it replaces — a loop inside a loop over the same array — is the first thing most people write.

Take a sorted array [2, 7, 11, 15] and a target of 9. Checking every pair means six sums. With one finger on the smallest value and one on the largest, you need three, and on an array of 100,000 values the gap becomes 100,000 steps against five billion. This lesson explains why that works, when it applies, and the three shapes it takes.

The intuition: two ends of a sorted shelf

The analogy holds only because the shelf is sorted. If prices were in random order, "too expensive" would tell you nothing about the neighbours, and moving a hand would throw away items that might have worked.

How to recognise it

Four signals in the problem statement:

1. The input is sorted, or you may sort it. This is the loudest signal. Sorted order means one comparison at the ends tells you something about everything in between.
2. You want a pair, a triplet, or two positions. "Two values that add to the target", "three numbers that sum to zero", "the two lines that hold the most water".
3. The question is symmetric from both ends. Palindrome checks are the clearest case: the first character must match the last, the second the second-to-last, and so on.
4. An in-place rearrangement is required. "Remove duplicates in place and return the new length", "move all zeroes to the end". Here one pointer reads and the other writes.

And one signal in the constraints: n up to 10⁵ or more with an obvious O(n²) pair search. That rules out checking every pair and asks for O(n) or O(n log n).

When the signal is absent. Two pointers on an unsorted array is the most common misfire. The argument for moving a pointer depends on knowing that everything to the right is larger. On unsorted input a move eliminates nothing, and the code returns wrong answers that look plausible on small tests. If order does not matter to the answer, sort first for O(n log n). If the answer depends on original positions — "return the indices in the original array" — sorting destroys that information, and a hash map is usually the better tool.

How it works: an elimination argument

Run the sorted array [2, 7, 11, 15] with target 9. Start with left = 0 and right = 3, and at each step compare numbers[left] + numbers[right] with the target.

Slow down on step 1, because every later pattern in the course uses the same style of argument. The sum is 17, too big. Could 15 be part of the answer with some other partner? Its partner would have to come from [2, 7, 11]. But 2 is the smallest of those, and 2 + 15 already overshoots. Every other partner is larger, so every pair containing 15 overshoots. One comparison removed 15 and all three of its pairs.

The mirror argument runs when the sum is too small: numbers[left] paired with the largest remaining value still falls short, so no partner can rescue it, and left advances.

Picture all pairs as a table, with left choosing the row and right the column. The brute force visits every cell. Two pointers deletes a whole row or a whole column with each comparison. That is the engine of the pattern.

Termination. The loop runs while left < right. When the pointers meet, every pair has been checked directly or ruled out, so there is no answer. Using left <= right would pair an element with itself — a different problem, and a common bug.

The three arrangements

"Two pointers" is really three arrangements that share a name. Knowing which one a problem wants is most of the work, because the loop condition and the movement rule both follow from it.

The templates

Three templates, one per arrangement. Read the loop conditions carefully; they are where the bugs live.

1def converging(numbers: list[int], target: int) -> list[int]:2    """Return 0-based indices [i, j] with numbers[i] + numbers[j] == target, or []."""3    left, right = 0, len(numbers) - 14    while left < right:                  # two different elements5        current = numbers[left] + numbers[right]6        if current == target:7            return [left, right]8        if current < target:9            left += 1                    # need a bigger sum; numbers ascend10        else:11            right -= 1                   # need a smaller sum12    return []                            # pointers met: no pair exists

Line by line: the pointers start at the two ends. Each round computes one sum. Equal means done. Too small means the left value is hopeless, so left moves. Too big means the right value is hopeless, so right moves. The direction comes from the sort order — on a descending array both branches flip — so derive it each time rather than memorising it.

1def remove_value(numbers: list[int], unwanted: int) -> int:2    """Remove every copy of `unwanted` in place; return the new length."""3    write = 0                            # next slot for a kept element4    for read in range(len(numbers)):5        if numbers[read] != unwanted:6            numbers[write] = numbers[read]7            write += 1                   # moves only when we keep something8    return write                         # length of the cleaned prefix

The invariant is worth saying out loud in an interview: everything in numbers[0:write] is a kept element, in the original order. Because write never passes read, you never overwrite an element you have not read yet. On [3, 1, 3, 2, 3, 4] with unwanted = 3 it returns 3, and the list becomes [1, 2, 4, 2, 3, 4]. Only the first 3 slots matter; anything past the returned length is leftover, which these problems allow.

1def merge_sorted(a: list[int], b: list[int]) -> list[int]:2    """Merge two ascending lists into one ascending list."""3    i, j = 0, 04    merged: list[int] = []5    while i < len(a) and j < len(b):6        if a[i] <= b[j]:7            merged.append(a[i])          # the smaller head goes next8            i += 19        else:10            merged.append(b[j])11            j += 112    merged.extend(a[i:])                 # drain whatever is left13    merged.extend(b[j:])14    return merged

The rule for two arrays is always "advance the pointer at the smaller value", because that value cannot be matched or placed by anything later in the other array. The two extend lines drain the leftovers; forgetting them is the classic bug.

A fourth shape: three pointers. Sorting an array that holds only 0, 1 and 2 in one pass (the "Dutch national flag" problem) stretches the idea to three indices: low marks the end of the 0s, high the start of the 2s, and current scans between them.

1def sort_three_values(colours: list[int]) -> None:2    """Sort a list holding only 0, 1 and 2 in place, in one pass."""3    low, current, high = 0, 0, len(colours) - 14    while current <= high:               # colours[high] is not yet examined5        if colours[current] == 0:6            colours[low], colours[current] = colours[current], colours[low]7            low += 18            current += 19        elif colours[current] == 2:10            colours[current], colours[high] = colours[high], colours[current]11            high -= 1                    # do not advance current: new value unseen12        else:13            current += 1

The asymmetry is the whole trick. A value swapped in from low has already been scanned, so current moves on. A value swapped in from high has not, so current stays and checks it.

Complexity

Converging: each round moves one pointer one step inward, and the gap between them starts at n − 1, so there are at most n − 1 rounds of constant work: O(n) time, O(1) space. Parallel: read visits each element once: O(n) time, O(1) space. Two arrays: each round advances at least one pointer, so at most m + n rounds: O(m + n) time, and O(1) beyond the output. If you have to sort first, add O(n log n) time, which then dominates.

Against the brute force's O(n²) at n = 100,000, converging pointers do about 100,000 steps instead of about five billion.

Where it goes wrong

Five bugs produce nearly every failing two-pointer solution. Learn them as a checklist.

1. The wrong loop condition. while left <= right lets the pointers land on the same element. On [3, 5] with target 6 it returns [0, 0] — 3 + 3, using one element twice. Use left < right when the two positions must differ; use <= only when one remaining element still needs work, as with current <= high in the three-value sort.
2. Moving both pointers when only one is proven useless. On [1, 2, 8, 11] with target 9, the first sum 1 + 11 = 12 is too big. Moving both pointers jumps to 2 + 8 and throws away 1, which was half of the answer 1 + 8. The code returns "no pair". Ask after every comparison: which element is proven impossible? Move only that one.
3. Unsorted input. On [7, 2, 15, 11] with target 9 the converging template happens to return [0, 1]. On [15, 2, 7, 11] it returns nothing, although 2 + 7 = 9. Tests pass, the interview does not. Before coding, say: "the array is sorted, so moving right left makes the sum smaller." If that sentence is false, stop.
4. A branch that moves nothing. If any branch of the if chain leaves both pointers where they are, the loop never ends. Check each branch.
5. Off-by-one at the edges. right = len(numbers) instead of len(numbers) - 1 fails with an index error. Returning write - 1 as a length is one short, because write is already a count.

Duplicates add a sixth trap in problems that return all answers, such as 3Sum: equal values produce the same answer twice unless you skip them. The 3Sum lesson covers exactly where the skips go.