Patterns / Two Pointers

Two Pointers Pattern

Two indices walking through the data examine each element once, replacing an O(n²) "every pair" loop.

What it is

The two-pointers technique keeps two indices into a sequence and moves them based on the comparison at hand — either toward each other from both ends, or together at different speeds. Because each pointer only moves forward, the whole scan is linear even though it is answering a question that looks quadratic. It shines on sorted data, where the comparison at the two ends tells you unambiguously which pointer to advance.

When to use it — the signals

A sorted array plus "find a pair/triplet with a given sum".
Palindrome checks or comparing a sequence from both ends.
"Do it in place with O(1) extra space" (e.g. remove duplicates, move zeroes).
Merging or partitioning two ordered sequences.

How it works

A representative implementation in Java:

// Pair summing to target in a SORTED array.
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
    int sum = nums[lo] + nums[hi];
    if (sum == target) return new int[]{ lo, hi };
    if (sum < target) lo++;   // need a bigger value
    else hi--;                // need a smaller value
}
return new int[]{ -1, -1 };

Complexity

O(n) for the scan itself; O(n log n) overall if you must sort first. Space is O(1).

Common pitfalls

Applying it to unsorted data when the logic relies on order.
Off-by-one errors in the while condition (lo < hi vs lo <= hi).
Skipping duplicates incorrectly in triplet problems, producing repeats.

Practice problems

Classic problems where this pattern is the intended approach: Valid Palindrome, Two Sum II (sorted), 3Sum, Container With Most Water. Work through them on the Leet Study home page.

← All patterns