Two pointers on sorted data¶

~20 min · prerequisite: Counting steps and choosing a Python interpreter

What you will be able to do¶

Use two indices that move through a sorted list, and explain why each move is safe.
Show that a two-pointer loop takes at most n - 1 steps, using the gap between the indices.
Avoid the common off-by-one errors when the two indices meet.

The idea¶

The two pointers technique keeps two indices into a sequence, usually called l for left and r for right. At each step, a comparison tells you which index to move. The technique works on sorted data, because sorting gives you a rule for which index can be moved safely.

Here is the problem. You have a sorted list and a target. Is there a pair of different positions whose values add up to the target? A slow method checks every pair, which takes about n² steps. The two-pointer method starts with l at the smallest value and r at the largest value. Compare their sum s with the target.

If s equals the target, you have found a pair. If s is smaller than the target, the value at l cannot be the answer with any partner, because even its largest possible partner, the value at r, is still too small. So you move l one step right. If s is larger than the target, the value at r cannot pair with anything, so you move r one step left. Each move discards one index for good.

Why does the loop finish quickly? Look at the gap r - l. It starts at n - 1, and every step makes it one smaller, because one pointer moves inward. The loop stops when the gap is zero. So the loop runs at most n - 1 times, which is O(n). The sort itself costs about n log2(n) steps, so the total is dominated by the sort.

Worked example¶

The function below returns True when two positions in a sorted list add up to the target.

def has_pair_with_sum(values, target):
    l, r = 0, len(values) - 1
    while l < r:
        s = values[l] + values[r]
        if s == target:
            return True
        if s < target:
            l += 1
        else:
            r -= 1
    return False


assert has_pair_with_sum([1, 3, 4, 6, 8], 10) is True

Line by line, this is what Python does with [1, 3, 4, 6, 8] and target 10:

l, r = 0, len(values) - 1 sets l to index 0, the value 1, and r to index 4, the value 8.
The loop runs while l < r. The condition stops the loop when the indices meet, so a value is never paired with itself.
The sum 1 + 8 is 9, which is less than 10. So l moves to index 1.
The sum 3 + 8 is 11, which is more than 10. So r moves to index 3.
The sum 3 + 6 is 9, which is less than 10. So l moves to index 2.
The sum 4 + 6 is 10. The function returns True.

The loop took four steps. The list had five values, so the bound of n - 1 holds.

Try it¶

The first block checks the pair function on a few inputs. The second counts pairs whose sum is at most a limit. When a pair fits, every position between the pointers also fits with the left pointer, so the block adds r - l at once.

def has_pair_with_sum(values, target):
    l, r = 0, len(values) - 1
    while l < r:
        s = values[l] + values[r]
        if s == target:
            return True
        if s < target:
            l += 1
        else:
            r -= 1
    return False


assert has_pair_with_sum([1, 3, 4, 6, 8], 10) is True
assert has_pair_with_sum([1, 9, 2, 8], 10) is False
assert has_pair_with_sum([5], 10) is False

def count_pairs_at_most(values, limit):
    l, r = 0, len(values) - 1
    count = 0
    while l < r:
        if values[l] + values[r] <= limit:
            count += r - l
            l += 1
        else:
            r -= 1
    return count


def brute(values, limit):
    n = len(values)
    return sum(1 for i in range(n) for j in range(i + 1, n) if values[i] + values[j] <= limit)


assert count_pairs_at_most([1, 2, 3, 4], 5) == brute([1, 2, 3, 4], 5)
assert count_pairs_at_most([1, 2, 3, 4], 5) == 4
assert count_pairs_at_most([1, 1, 1], 2) == 3

Common mistakes¶

Giving the function unsorted input. No error appears, but the answer can be wrong. The pair 1 + 9 exists in [1, 9, 2, 8], yet has_pair_with_sum([1, 9, 2, 8], 10) returns False. The rule for moving pointers depends on sorted order, so call sorted(values) first.

Using <= in the loop condition. With while l <= r, one value can be paired with itself. The single value 5 then appears to make 10:

def has_pair_loose(values, target):
    l, r = 0, len(values) - 1
    while l <= r:
        s = values[l] + values[r]
        if s == target:
            return True
        if s < target:
            l += 1
        else:
            r -= 1
    return False


assert has_pair_loose([5], 10) is False

AssertionError

Keep while l < r when the two indices must be different positions.

Moving a pointer past the end. A loop that moves l without checking the length fails when it reaches the end:
```
values = [1, 2]
i = 0
while values[i] < 10:
    i += 1
```
```
IndexError: list index out of range
```
Add the bound to the loop condition, such as while i < len(values) and values[i] < 10.
Forgetting to move a pointer. If one branch does not change l or r, the loop never ends. On a judge this shows up as Time limit exceeded. Check that every branch of the loop moves at least one pointer.

Practice¶

Easy: write has_adjacent_duplicate(values) for a sorted list. It returns True when two neighbouring values are equal. Check has_adjacent_duplicate([1, 2, 2]) is True.
Easy: write count_removed(values) that returns how many values unique_sorted removes. Check count_removed([1, 1, 2, 2, 2, 3]) is 3.
Medium: write has_difference(values, t) for a sorted list and a value t >= 0. It returns True when two different positions differ by exactly t. Check has_difference([1, 4, 9], 5) is True.
Medium: write merge_sorted(a, b) that merges two sorted lists into one sorted list using two indices. Check merge_sorted([1, 4], [2, 3]) equals [1, 2, 3, 4].
Stretch: write count_pairs_at_most from the second runnable block without a brute-force helper, and check it against brute on [1, 2, 2, 5, 7] with limit 6.

Solution

```python def has_adjacent_duplicate(values): for i in range(len(values) - 1): if values[i] == values[i + 1]: return True return False

assert has_adjacent_duplicate([1, 2, 2]) is True ```

```python def count_removed(values): return len(values) - len(set(values))

assert count_removed([1, 1, 2, 2, 2, 3]) == 3 ```

In a sorted list, every repeated value is a duplicate, so the set has one entry per distinct value.

```python def has_difference(values, t): l, r = 0, 0 n = len(values) while r < n: if l == r: r += 1 continue d = values[r] - values[l] if d == t: return True if d < t: r += 1 else: l += 1 return False

assert has_difference([1, 4, 9], 5) is True ```

```python def merge_sorted(a, b): i = j = 0 out = [] while i < len(a) and j < len(b): if a[i] <= b[j]: out.append(a[i]) i += 1 else: out.append(b[j]) j += 1 out.extend(a[i:]) out.extend(b[j:]) return out

assert merge_sorted([1, 4], [2, 3]) == [1, 2, 3, 4] ```

```python def count_pairs_at_most(values, limit): l, r = 0, len(values) - 1 count = 0 while l < r: if values[l] + values[r] <= limit: count += r - l l += 1 else: r -= 1 return count

assert count_pairs_at_most([1, 2, 2, 5, 7], 6) == 4 ```

The pairs with sum at most 6 are (1, 2), (1, 2), (1, 5) and (2, 2), so the answer is 4. The brute helper from the second runnable block gives the same count.

Recap¶

Two pointers on sorted data let each comparison discard one index for good.
The gap r - l shrinks by one every step, so the loop takes at most n - 1 steps.
Keep while l < r for distinct positions, and check that every branch moves a pointer.