Two Pointers

Walk an array from both ends, or at two speeds, instead of nesting loops.

The idea

Two pointers is the other common way a nested loop collapses into a single pass — and it is the one to reach for when a hash map would be overkill or the data is already sorted.

Two shapes cover most of it:

Converging. One index at each end, moving toward each other. Each step rules out one candidate permanently, which is why a sorted array can be searched in one pass instead of n².
Same-direction. Both indices move forward, one faster than the other. This is how you detect a cycle, remove duplicates in place, or maintain a window.

The thing that makes it work is an invariant: something true before and after every step. In converging search over a sorted array, the invariant is "the answer, if it exists, lies between the two pointers." Every move preserves that, which is why discarding the rest is safe.

If you cannot state the invariant, the pointers are guesswork.

Walkthrough

Watch the two pointers converge, swapping as they go.

What it costs

time: O(n) for a single pass
space: O(1) — the pointers are the only extra state

Often the reason to prefer this over a hash map: same linear time, but constant space instead of O(n). If the input needs sorting first, that sort dominates at O(n log n).

When to reach for it

The array is sorted, or can be sorted without losing what you need.
You are looking for a pair, a triple, or a partition point.
You want O(1) extra space where a hash map would cost O(n).
Something is being compared from both ends inward, or two sequences are being merged.

Rather than the obvious alternative

A hash map

For pair-sum on an unsorted array the map is O(n) and two pointers is O(n log n) because of the sort. Two pointers wins when the input is already sorted, or when O(1) space is required.

A nested loop

The technique exists to remove exactly this: both pointers only move forward, so each element is handled a constant number of times.

How to spot it

The array is sorted, or sorting it would not lose information you need.
You are looking for a pair, a triplet, or a subarray that satisfies a condition.
The problem asks you to do it in constant extra space.
You need to compare elements from opposite ends, or detect a cycle.

Where it goes wrong

Moving both pointers at once

In a converging search you move exactly one per step — the one whose move can improve the result. Moving both can step over the answer.

Off-by-one at the meeting point

Decide deliberately whether the pointers may land on the same index. `while (i < j)` and `while (i <= j)` solve different problems.

Reaching for it on unsorted data

Converging pointers rely on order to know which way to move. Without it, use a hash map instead.

Try it

Two short checks. They run the same way the practice problems do — write the function, press Run.

Reverse xs without allocating a new array. Converging pointers, swapping as they meet.

Or press ⌘↩

Tests

4 cases, 1 hidden

call	type	expected	result
reverse([1,2,3,4])	even length	[4,3,2,1]	—
reverse([1,2,3])	odd length	[3,2,1]	—
reverse([9])	single element	[9]	—
withheld	hidden	withheld	—

Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.

Hints

Stuck? Hints open one at a time, each giving a little more away.

2 hints left

Given a sorted array and a target, return the indices of the two values that sum to it, or []. Constant extra space — no map.