Introduction to Two Pointers Pattern

The Two Pointers Pattern

When a problem asks you to find a pair (or triple) of elements in a sorted array that satisfy some condition, the naive move is two nested loops — test every pair, O(n²). The two-pointers pattern collapses that to one linear pass: place two indices on the array and move them toward each other, and because the array is sorted, each move lets you rule out a whole set of pairs at once instead of one at a time.

There are two flavours of the pattern:

• Converging (opposite ends) — left at the start, right at the end, walking inward. Needs a sorted array for pair-sum and its relatives. Also used for container-with-most-water and palindrome checks — container-with-most-water is the odd one out: it needs no sorting, and its safety argument differs from pair-sum's (always move the shorter line: the area is capped by the shorter height, so keeping the shorter side while the width shrinks can never produce a bigger container). This page focuses here.
• Fast / slow (same direction, different speeds) — two pointers advancing at different rates on the same end. Used for cycle detection (Floyd), finding the middle of a linked list, and in-place dedup. No sortedness required.

The mechanism (converging)

Keep left and right. Compute the quantity you care about (say the sum). Compare it to the target: if you need it bigger, the only useful move is left++ (the next value up); if you need it smaller, right--. One comparison, one pointer step — and everything you skipped is provably out of range because the array is ordered.

Recognize the pattern — the tells

• You need a pair / triple / subarray that meets a condition, and the array is sorted (or you can sort it).
• The obvious solution is a nested loop over all pairs — O(n²).
• The quantity is monotonic in the pointer positions: moving a pointer predictably raises or lowers it. That monotonicity is what makes discarding a whole side safe.

Traced example — pair with target sum 15

Array [1, 3, 4, 6, 8, 11, 15], target 15:

Code

int[] pairWithTargetSum(int[] arr, int target) {
    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++;      // need a bigger sum
        else               right--;     // need a smaller sum
    }
    return new int[]{-1, -1};
}

Complexity — from first principles

left only ever increases and right only ever decreases, and they stop when they meet. So the total number of moves is bounded by the gap they start with:

moves ≤ right - left = n - 1   →   time = O(n)
extra memory = two indices        →   space = O(1)

Compare the brute force: (n choose 2) ≈ n²/2 pairs, O(n²). Two pointers is a full order faster, and unlike the hash-set approach (also O(n) time) it uses O(1) space — the trade you make is that the array must be sorted.

Pitfalls

• Unsorted input. The monotonic argument only holds on sorted data. On unsorted input you must sort first (adds O(n log n)) or switch to a hash set.
• Pointer crossing. Loop while left < right. Using ≤ can pair an element with itself.
• Duplicates (3Sum family). After fixing one element and two-pointering the rest, skip equal neighbours or you will emit duplicate triples.
• Wrong pointer moved. The move direction comes from the monotonic relationship — always be able to say why moving this pointer helps, or you will loop forever.

When to use it — and when not

• vs. nested loops: two pointers is O(n) vs O(n²). Always prefer it when the array is sorted and the quantity is monotonic.
• vs. hash set: a hash set also finds pair-sums in O(n) time but costs O(n) space and works on unsorted input. Choose two pointers when the array is already sorted (or sorting is cheap/needed anyway) and you want O(1) space.
• vs. sliding window: sliding window is for contiguous subarrays; two pointers is for pairs at a distance (converging) or traversal invariants (fast/slow). If the answer is a contiguous run, reach for sliding window instead.
• Don't use converging two pointers when the quantity is not monotonic in the pointers (then moving a pointer tells you nothing) — that is a different technique.

Takeaways

• Two pointers turns O(n²) pair-search into O(n) by discarding a whole side per comparison.
• The move rule is the monotonicity argument — state why the discard is safe.
• Converging needs a sorted array; fast/slow does not.
• O(n) time, O(1) space — beats the hash-set approach on memory.

Re-authored and deepened for this guide. Sources: DesignGurus “Grokking the Coding Interview” (pattern framing) and standard first-principles treatment of the monotonic-discard argument and complexity.