Two Pointers

Two indexes walk through an array, string or linked list, and each move rules out many answers at once. It often turns an O(n²) pair search into one O(n) pass with O(1) extra space.

Overview

The idea

A brute-force pair search checks every pair with two nested loops, which is O(n²). The two-pointer technique keeps two indexes instead and moves one of them on each step. Each move is safe because the structure of the input (sorted order, or a rule about what to keep) proves that the skipped pairs cannot be the answer. So the whole input is walked once.

There are four common shapes.

Opposite ends — first and last index — toward each other — Two Sum II, Container With Most Water, palindromes
Read and write — both at the start — read moves every step, write only when a value is kept — Remove Duplicates, Move Zeroes, Remove Element
Fast and slow — both at the head — slow moves 1 node, fast moves 2 — Linked List Cycle, middle of a list
Two inputs — one pointer per input — the pointer at the smaller value moves — Merge two sorted arrays, Is Subsequence

Sliding window is a close relative where the two pointers mark the ends of a range; it has its own topic.

Opposite ends: why a move is safe

Take a sorted array and a target sum. Put the left pointer on the smallest value and the right pointer on the largest. If the sum is too big, the only way to shrink it is to move right inward. If it is too small, move left inward.

The proof in one sentence: when the sum is too big, a[R] plus the smallest value still in play is already too big, so a[R] cannot be part of any answer and can be dropped. The same holds for a[L] when the sum is too small.

The trace below runs on [1, 3, 5, 7, 9, 11, 15] with target 14.

1 — 0 — 6 — 1 — 15 — 16 — too big, move R left
2 — 0 — 5 — 1 — 11 — 12 — too small, move L right
3 — 1 — 5 — 3 — 11 — 14 — found

Three checks instead of the 21 pairs a nested loop would try.

Read and write: filtering in place

The read pointer visits every element. The write pointer marks where the next kept element goes. Everything left of the write pointer is the finished answer, and the order of kept elements does not change.

Trace for removing duplicates from the sorted array [0, 0, 1, 1, 1, 2]. Write starts at 1 because the first element is always kept.

1 — 0 — 1 — no, same as a[0] — 0 0 1 1 1 2 — 1
2 — 1 — 1 — yes — 0 1 1 1 1 2 — 2
3 — 1 — 2 — no — 0 1 1 1 1 2 — 2
4 — 1 — 2 — no — 0 1 1 1 1 2 — 2
5 — 2 — 2 — yes — 0 1 2 1 1 2 — 3

The answer is the first 3 slots, [0, 1, 2]. What sits after them does not matter.

Fast and slow: finding a cycle

On a linked list you cannot index from the end, so both pointers start at the head. Slow moves one node per step and fast moves two. With no cycle, fast reaches the end. With a cycle, fast gains one node per step on slow inside the loop, so it must land on slow. This is usually called Floyd's tortoise and hare. Knuth credited it to Robert W. Floyd, though it may be folklore.

0 — 1 — 1
1 — 2 — 3
2 — 3 — 5
3 — 4 — 3
4 — 5 — 5 (meet)

To find where the cycle starts, move one pointer back to the head and step both one node at a time. They meet at the cycle start. Here: from 1 and 5, then 2 and 6, then 3 and 3.

Why it works. Let L be the distance from the head to the cycle start, C the cycle length and K the distance from the cycle start to the meeting point. Slow walked L + K and fast walked twice that. The extra L + K is a whole number of laps, m times C. So L = mC minus K: walking L steps from the meeting point ends at the cycle start. In the example L = 2, C = 4, K = 2.

Three pointers: partition in one pass

Sort Colors (the Dutch national flag problem, posed by Edsger Dijkstra in 1976) sorts an array of 0s, 1s and 2s in one pass. Three indexes split the array into four regions.

Left — 0 to low - 1 — 0s
Middle — low to mid - 1 — 1s
Unknown — mid to high — not looked at yet
Right — high + 1 to end — 2s

At each step the algorithm looks at a[mid]. A 0 is swapped to low, and both low and mid move on. A 1 stays, and mid moves on. A 2 is swapped to high and high moves back, but mid stays, because the value that came from high has not been looked at yet.

The trace below runs on [2, 0, 2, 1, 1, 0].

0, 0, 5 — 2 — swap with high, high - 1 — 0 0 2 1 1 2
0, 0, 4 — 0 — swap with low, low + 1, mid + 1 — 0 0 2 1 1 2
1, 1, 4 — 0 — swap with low, low + 1, mid + 1 — 0 0 2 1 1 2
2, 2, 4 — 2 — swap with high, high - 1 — 0 0 1 1 2 2
2, 2, 3 — 1 — mid + 1 — 0 0 1 1 2 2
2, 3, 3 — 1 — mid + 1, loop ends — 0 0 1 1 2 2

Spotting a two-pointer problem

Sorted array, find a pair or triplet with a sum — opposite ends (fix one element for triplets)
Modify the array in place, keep the order, O(1) space — read and write
Linked list: cycle, middle, k-th from the end — fast and slow
Two sorted inputs to merge or compare — one pointer per input
Group values into two or three classes in place — partition with two or three pointers
Palindrome or reverse in place — opposite ends

> [!TIP] > If the array is not sorted and the question wants indexes, sorting would lose them. A hash map is usually the better tool there.

What you will be able to do

Pick the right variant from the wording of a problem.
Explain why each pointer move never skips a valid answer.
Trace a solution on a small input, step by step, at the whiteboard.
Write Two Sum II, Three Sum, Container With Most Water, Sort Colors and cycle detection without bugs.
State the time and space cost, including the cost of sorting first.

When to use it

Sorted array problems that ask for a pair or triplet meeting a condition
Detecting a cycle, or its start, in a linked list
Finding the middle of a linked list, or the k-th node from the end
Removing or moving elements in place while keeping their order
Palindrome checks and in-place reversal
Three Sum and K-Sum: fix elements with loops, then run two pointers on the rest

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio