Two pointers

You’ll recognise it when

• The array is sorted, or sorting it doesn’t lose anything you need, and you want two values that add up to (or come closest to) a target.
• A brute force would try every pair, O(n²), and you need O(n).
• You’re asked for triples (3-sum) or the best pair of positions, like the widest or largest container.
• You must do it in place, with O(1) extra memory, so a hash map is off the table.

It’s often confused with the sliding window, where both pointers move the same way to track a contiguous stretch. Here they start at opposite ends and walk towards each other.

The idea

You and a friend want to spend exactly $20 on two different items from a price list sorted from cheap to expensive. Start with the cheapest and the priciest. Too expensive? The priciest item is hopeless: even with the cheapest item it’s over budget, so cross it off. Too cheap? The cheapest item is hopeless: even with the priciest item it falls short, so cross that off instead.

That’s the whole trick. Each comparison tells you which end can’t be in any pair, so you drop it and never look at it again. The two pointers close in until they find the pair or meet.

How it works

left starts at the first index and right at the last. Scroll through the steps and the graphic follows along; you can also press play, or edit the input and try a target with no pair.

Why no pair is ever skipped: every pair that works stays between left and right. When total < target, a[right] is the largest value still in play, so a[left] plus anything else in range is also too small; a[left] belongs to no answer. The same argument in mirror image covers total > target. Each move throws away only a value that was provably useless.

def pair_with_sum(a, target):
    """Indices (i, j) with i < j and a[i] + a[j] == target, or (-1, -1).
    a must be sorted in ascending order."""
    left, right = 0, len(a) - 1
    while left < right:
        total = a[left] + a[right]
        if total == target:
            return left, right
        # Drop the end that can't be part of any pair.
        if total < target:
            left += 1
        else:
            right -= 1
    return -1, -1

#include <utility>
#include <vector>
using namespace std;

// Indices {i, j} with i < j and a[i] + a[j] == target, or {-1, -1}.
// a must be sorted in ascending order.
pair<int, int> pairWithSum(const vector<int>& a, int target) {
    int left = 0, right = (int)a.size() - 1;
    while (left < right) {
        long long total = (long long)a[left] + a[right];
        if (total == target) {
            return {left, right};
        }
        // Drop the end that can't be part of any pair.
        if (total < target) {
            left++;
        } else {
            right--;
        }
    }
    return {-1, -1};
}

class TwoPointers {
    // Indices {i, j} with i < j and a[i] + a[j] == target, or {-1, -1}.
    // a must be sorted in ascending order.
    static int[] pairWithSum(int[] a, int target) {
        int left = 0, right = a.length - 1;
        while (left < right) {
            long total = (long) a[left] + a[right];
            if (total == target) {
                return new int[] {left, right};
            }
            // Drop the end that can't be part of any pair.
            if (total < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[] {-1, -1};
    }
}

Why it’s O(n)

Every step either returns or moves one pointer one place inwards, so the gap right - left shrinks by 1 each time. It starts at n - 1, which means at most n - 1 sums. Two integers of state make the space O(1).

Picture all pairs as a triangle of cells, row i and column j. Each move rules out a whole row (dropping left) or a whole column (dropping right), which is why n steps are enough to cover n² / 2 pairs.

If the input isn’t sorted, sorting first costs O(n log n), and that dominates.

Common mistakes

while left <= right:   # ✗ can use one element twice
while left < right:    # ✓ two different positions

int total = a[left] + a[right];                  // ✗ wraps around
long long total = (long long)a[left] + a[right]; // ✓ fits

a.sort()                                           # ✗ original positions lost
order = sorted((v, i) for i, v in enumerate(a))    # ✓ keep them alongside

Variations

• 3-sum. Sort, then fix each value as an anchor and run two pointers on the part after it, looking for -anchor. O(n²) in total. Skip anchors equal to the previous one to avoid duplicate triples.
• Container with most water. Pointers at both ends; the area is the shorter height times the width. Always move the shorter side: any container that keeps it is narrower and no taller, so it can’t win.
• Removing duplicates in place. Both pointers go left to right: a fast one reads every value, a slow one marks where the next unique value gets written.
• Reversing and palindromes. Swap or compare a[left] and a[right], then step both inward until they meet.
• Fast and slow pointers. On a linked list, one pointer moves two steps for each step of the other. When the fast one reaches the end, the slow one is at the middle; if they ever meet, the list has a cycle (Floyd’s algorithm).