Two Pointers

Most people meet two pointers as a trick for one specific problem — find a pair in a sorted array that sums to a target — and never generalise it past that. It's worth generalising, because the same idea underlies sliding windows, cycle detection, in-place array partitioning, and merging two sorted sequences. All of it is one observation: if moving an index can only ever help in one direction, you never need to move it back.

The idea

A brute-force pair search checks every (i, j) combination — O(n²). Two pointers replaces that with two indices that each move at most n times in total, for O(n) — provided the data has some structure the pointers can exploit. Almost always, that structure is sorted order or monotonicity: some property of the window between the pointers only increases as one pointer moves right, and only decreases as the other moves left.

That's the part worth internalising, because it's also the check for whether two pointers applies at all: can you argue that skipping the position you're about to skip is always safe? If yes, you have a two-pointer solution. If the answer is "it depends on what's later in the array," you don't — you need a hash map, a stack, or something else that can look backward.

Two shapes

Opposite ends, closing inward. Start left = 0, right = n - 1. On a sorted array looking for a pair that sums to target: if the current sum is too small, the only way to increase it is to move left right (every element left of the old left is smaller than what's already there, so pairing with any of them is strictly worse). If it's too large, move right left, by the same argument in reverse. Either way, one comparison eliminates one whole index permanently.

int left = 0, right = arr.length - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == target) return new int[] { left, right };
    if (sum < target) left++;
    else right--;
}

Fast and slow, same direction. Both pointers start at 0 and only ever move right; the gap between them is the "window." This is the shape behind sliding-window problems (longest substring without repeating characters, smallest subarray with a sum at least k) and in-place array editing (remove duplicates from a sorted array, partition around a pivot). The invariant here is usually "everything the slow pointer has already passed satisfies some property" — and the fast pointer's job is to find the next place that's no longer true.

int slow = 0;
for (int fast = 0; fast < arr.length; fast++) {
    if (arr[fast] != arr[slow]) {
        slow++;
        arr[slow] = arr[fast];
    }
}
// arr[0..slow] is now the deduplicated prefix

A cycle detector (Floyd's) is the same shape with the pointers moving at different speeds instead of starting at different positions — worth recognising as a relative of this family rather than an unrelated trick, since the reason it terminates is the same kind of monotonic argument: the gap between fast and slow only shrinks, mod the cycle length, once both are inside the loop.

Complexity

Both shapes are O(n) time, O(1) extra space — the entire appeal next to a hash-map approach that solves the same problem in O(n) time but O(n) space. That trade is exactly what an interviewer is checking when they ask "can you do it without extra space" after you've produced a correct hash-map solution: they want to see whether you notice the input is sorted (or can be sorted for an O(n log n) cost that still beats the space trade-off) and reach for this instead.

What interviewers push on

• "What if the array isn't sorted?" Either sort it first (O(n log n), often still the right call), or recognise the problem doesn't have the monotonicity property at all and a hash map is the honest answer — saying "two pointers, but I'll sort first" without noticing the complexity moved is a common half-credit answer.
• Duplicate handling. Opposite-ends pair-sum variants that must return all pairs, not just one, need an explicit "skip past duplicates" step after a match — forgetting it is the single most common bug in this family, not an off-by-one in the loop bound.
• Three pointers. 3Sum is two pointers wrapped in an outer loop: fix one index, then run the opposite-ends pattern on the remainder. If you can explain why the inner part is still O(n) (not O(n²)) per outer iteration, that's usually the signal an interviewer is listening for — the whole solution is O(n²), not the O(n³) a first instinct produces.

Real-world use

• The merge step of merge sort, and merging any two already-sorted sequences — two log files ordered by timestamp, two sorted query results — is the opposite-ends shape's same-direction cousin: a pointer into each sequence, always advancing whichever points at the smaller current element. It's the reason merge sort is O(n) per merge rather than something slower.
• A relational database's merge join. When both inputs to a join are already sorted on the join key (or the query planner sorts them because it's cheaper than the alternative), the engine walks both with two pointers, advancing whichever key is behind — exactly the opposite-ends comparison above, just comparing rows instead of array elements. It's one of the three join algorithms a real query planner chooses between (the others are hash join and nested-loop join), picked specifically when the inputs are already ordered.
• Partitioning, in quicksort and in partition-style array problems (move all evens before all odds, Dutch national flag), is the fast/slow shape: one pointer scans, the other marks the boundary of "everything verified so far."
• Diffing two sorted lists — which dependency versions changed between a lockfile and its predecessor, which rows are new in today's export versus yesterday's — is the opposite-ends shape again: whichever list's current element is "behind," advance it; a mismatch is a difference.

Practice it

The judge here runs these against hidden cases with measured runtime — a solution that's quietly O(n²) because of a missed early-exit still passes small samples and times out on the ones that matter.

Practice two-pointer problems