المؤشران (Two pointers)

Written Explanation

The idea: two walkers on a path

One walker starts at the left end, one at the right end. At each step you decide which walker moves. A walker never goes back. When they meet, the search is over.

In code the walkers are two int variables:

int l = 0;                 // left walker
int r = a.length - 1;      // right walker
while (l < r) {
    // look at a[l] and a[r], then move exactly one of them
}

The loop condition l < r means "the walkers have not met yet". Both walkers move in one direction only, so together they take at most n steps in total. That is where the O(n) cost comes from, as we will see below.

The pair-sum problem

Problem: the array a is sorted from small to large. Is there a pair of items whose sum is target?

The key observation uses the order of the data:

• a[l] is the smallest item still in play. a[r] is the largest.
• If a[l] + a[r] is too small, then a[l] is too small to pair with anything still in play: even the largest partner a[r] is not enough. So we can discard a[l] by moving l right.
• If the sum is too big, then a[r] is too big to pair with anything still in play: even the smallest partner is too much. Discard it by moving r left.
• If the sum equals target, we are done.

static boolean hasPair(int[] a, int target) {
    int l = 0, r = a.length - 1;
    while (l < r) {
        int sum = a[l] + a[r];
        if (sum == target) return true;
        if (sum < target) l++; else r--;
    }
    return false;
}

Every step discards one item for good, and we never need to look at it again. That is the whole trick: each decision removes a candidate, so no pair is tested twice.

Why the cost is O(n)

At the start the gap between the pointers is n - 1. Each loop iteration moves one pointer by one position, so the gap shrinks by exactly 1. The loop stops when the gap reaches 0, so it runs at most n - 1 times. Each iteration does a fixed amount of work. That is O(n) time. The method uses only a few int variables, so extra space is O(1). The nested-loop version checks about n × n / 2 pairs, which is O(n²) (BEG-039).

Why it needs sorted data

The argument "a[l] is too small to pair with anything" is only true because everything to the right of a[l] is at least as large as a[l], and everything is at most a[r]. If the array is not sorted, a[r] is not necessarily the largest item, so discarding a[l] can throw away the real answer. The technique does not crash on unsorted data. It just returns a wrong answer, which is worse.

You have three honest options when data is not sorted:

Second shape: both pointers go the same way

A second shape has a read pointer that scans every item and a write pointer that marks where the next kept item goes. It compacts an array in place.

Remove duplicates from a sorted array. Because the array is sorted, equal items sit next to each other. The item at index 0 is always kept. The write pointer w is the next free slot, so the last kept item is a[w - 1]. For each item at r, if it differs from a[w - 1] it is new, so copy it to a[w] and advance w.

static int removeDuplicates(int[] a) {
    if (a.length == 0) return 0;
    int w = 1;
    for (int r = 1; r < a.length; r++) {
        if (a[r] != a[w - 1]) a[w++] = a[r];
    }
    return w;   // the new length
}

The array is modified in place and no second array is needed. The method returns how many items are now valid at the front; anything after that index is leftover and should be ignored.

Reversing in place

Reversing is two pointers at its simplest: swap the two ends, then move both inward.

static void reverse(int[] a) {
    int l = 0, r = a.length - 1;
    while (l < r) {
        int t = a[l]; a[l] = a[r]; a[r] = t;
        l++; r--;
    }
}

This one does not need sorted data, because it never makes a decision based on values. The "needs sorted" rule applies to techniques that decide which pointer to move by comparing values.