Two pointers

Two indices walk a sorted array from opposite ends, and between them they answer a question about pairs in one pass instead of n² of them. The mechanism is three lines long. The part worth learning is the argument that makes those three lines correct, because without it the technique is a trick you either remember or do not.

What the pair scan wastes

The direct way to find two values summing to a target is to try every pair:

def two_sum_quadratic(a: list[int], target: int) -> tuple[int, int] | None:
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] + a[j] == target:
                return i, j
    return None

The innermost line runs n(n-1)/2 times. At n = 10⁵ that is about 5 × 10⁹ comparisons, and at roughly 10⁸ simple operations per second that is around 50 seconds — the same reading of the constraint that complexity by counting gives you before a line is written.

The waste is specific: when the array is sorted and a[i] + a[j] comes out too small, the loop goes on to try a[i] against every value below a[j] as well, every one of which is smaller. It already had the information that those comparisons would fail and it threw it away.

The proof is the whole technique

Sort the array ascending. Put l at index 0 and r at the last index, and look at a[l] + a[r].

If the sum is too small, take any index j with l < j ≤ r. Because the array is sorted, a[j] ≤ a[r], so a[l] + a[j] ≤ a[l] + a[r] < target. Index l is already paired with the largest partner still available and still falls short, so l appears in no remaining pair that can reach the target. Discarding it costs nothing. Move l right.

If the sum is too big, the mirror image: a[r] is paired with the smallest partner still available and still overshoots, so r is in no remaining pair that can work. Move r left.

If the sum equals the target, you have the answer.

Two pointers converging on a sorted array, discarding one index per step100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

Every iteration either finishes or removes one index from consideration forever, so there are at most n iterations. One comparison each, 10⁵ steps at n = 10⁵ — against 5 × 10⁹ for the pair scan, a factor of about 50,000.

def two_sum_sorted(a: list[int], target: int) -> tuple[int, int] | None:
    l, r = 0, len(a) - 1
    while l < r:
        s = a[l] + a[r]
        if s == target:
            return l, r
        if s < target:
            l += 1          # a[l] cannot reach the target with any partner left
        else:
            r -= 1          # a[r] overshoots even with the smallest partner left
    return None

If the input arrives unsorted, sorting first costs O(n log n) — about 1.7 million operations at n = 10⁵, which is still nothing beside 5 × 10⁹. Sorting is only the wrong move when the problem wants the original indices back and you have not carried them along, or when a hash map already answers the question in one unsorted pass.

The precondition, stated out loud

Two pointers need an ordering that makes moving one side provably safe. Not "the array is sorted" — sortedness is the usual way to get the property, not the property itself. What you actually need is that the quantity you compare against the target is monotone in each pointer: moving l right can only increase the sum, moving r left can only decrease it.

That is why the same code works for pair sums, for pair products once every value is non-negative, and for the inner scan of 3-sum after the outer index is fixed: in each, the tested quantity only rises as l moves right and only falls as r moves left. It silently fails the moment products are allowed negative values — then moving l right can send the product either way — or the array is "sorted" by a key unrelated to the quantity in the test. Say the monotonicity claim before writing the loop; this is the same discipline the solving loop asks for at step 4, and it is the step people skip.

Monotonicity is not the only licence to retire a pointer. The largest rectangle between two lines — area min(h[l], h[r]) * (r - l) — is not monotone in either end: on h = [1, 8, 6, 2, 5, 4, 8, 3, 7], moving l from 0 to 1 takes the area from 8 to 49, and from 1 to 2 takes it from 49 back to 36. The converging loop is still correct there, on a different, exchange-style argument: the shorter of the two lines caps the height of every pair it could ever belong to, and the width only shrinks from here, so that line is dead and gets discarded. Know which argument you are making: a discard argument has to be stated on its own terms, and monotonicity is not there to lean on.

Same-direction pointers

The second shape puts both pointers at the front and moves them at different speeds. A write pointer marks the boundary of the answer being built in place; a read pointer scans ahead. The invariant is a sentence: everything before w is a finished prefix of the answer, and everything from w up to rd has been examined and rejected.

Removing duplicates from a sorted array is that invariant with one condition:

def dedupe_sorted(a: list[int]) -> int:
    """Compact a in place; return the length of the unique prefix."""
    if not a:
        return 0
    w = 1                                  # a[:w] is unique and sorted
    for rd in range(1, len(a)):
        if a[rd] != a[w - 1]:              # compare against the last kept value
            a[w] = a[rd]
            w += 1
    return w

Partitioning is the same skeleton with a different test — keep everything that satisfies a predicate, in order, with no extra array:

def move_zeros(a: list[int]) -> None:
    w = 0
    for rd in range(len(a)):
        if a[rd] != 0:
            a[w], a[rd] = a[rd], a[w]
            w += 1

Both are O(n) time and O(1) extra space, and both read as one loop rather than two pointers, which is the point: the second pointer is a variable, not a control structure.

The variable-speed version of the same idea — expand one side, then pull the other side up until a condition holds again — is the sliding window, and it is worth reading straight after this one, because the safety argument there has the same shape.

In an interview

State the precondition before the code. "The array is sorted, so the sum is monotone in both pointers, which means when the sum is too small the left value is dead — it has already been tried against the largest partner available." That sentence is what is being graded; the loop that follows is bookkeeping.

Then give the complexity as a count, not a label: at most n pointer moves, one comparison each, O(n) after an O(n log n) sort.

The mistake that loses points: running two pointers on unsorted data because the shape of the problem looked familiar. The loop terminates, returns something, and passes the sample input often enough to feel right. When asked why moving l was safe, there is no answer, because there is not one.

The second most common: losing the original indices after sorting. If the question asks for positions, sort (value, index) pairs, or use a hash map instead and skip the sort entirely.

Check yourself

The array is sorted and a[l] + a[r] is larger than the target. Why is it wrong to move l right?

Moving l right can only make the sum larger, so it moves away from the target and skips over pairs that were never ruled out. The overshoot proves something about a[r], not about a[l]: r is the index that cannot appear in any workable pair, so r is the one that must move.

n = 10⁵ and the values are unsorted. Compare sorting plus two pointers against the pair scan, with numbers.

Sorting is about n log₂n ≈ 10⁵ × 17 ≈ 1.7 million operations, then the scan is 10⁵ more — call it 2 million. The pair scan is n(n-1)/2 ≈ 5 × 10⁹. At roughly 10⁸ operations per second that is 0.02 seconds against about 50 seconds.

You are asked to remove every element equal to a given value, in place, preserving order. Which pointer shape, and what is the invariant?

Same-direction, write and read. The invariant is that a[:w] holds the kept elements in their original order and everything from w to rd has been examined; the read pointer advances every step, the write pointer only on a keep. One pass, O(1) extra space.