---
title: 'Two Pointers'
source: 'https://academia.sh/en/courses/advanced-algorithms/two-pointers'
course: 'Advanced Algorithms and Problem Solving'
language: en
updated: '2026-08-17T18:07:30+00:00'
license: 'CC BY-SA 4.0'
---

# Two Pointers

Scanning from both ends of a sorted array; the 25 wrong answers that appear once the precondition breaks and the step cost of establishing that precondition.

The previous topic showed that an algorithm's correctness can be stated **probabilistically**:
expected performance is a distribution, a single run is one sample. This topic opens with a
different source of uncertainty, and this source is not probabilistic but **structural**.
Choosing a problem-solving pattern is not buying a speedup — it is **accepting a
precondition**.

As long as the precondition holds, the pattern is both correct and cheap. When it does not,
the pattern does not stop, does not warn, does not slow down — it **gives a wrong answer**,
and the wrongness cannot be read from the output. That is why all eight lessons of this
topic's eight build the same frame: an **oracle** (brute force, always correct, always
expensive), a **pattern**, and the **number of inputs where the two diverge**. The first
pattern is two pointers; its precondition is one sentence: **the array must be sorted**.

## Problem, Oracle, and Pattern

The problem is this: does a **pair of distinct positions summing to the target** exist in an
array. The oracle tries every pair; for an array of n values there are $n(n-1)/2$ pairs, and
when it must, the oracle looks at all of them. The pattern places two pointers at the array's
two ends, moves the left one right if the sum is below target, moves the right one left if it
is above.

**PP1.** The metric is **steps**, not time. The counter counts every comparison as one step,
and real time is measured nowhere.
**PP2.** The corpus comes from a deterministic generator; seed `20260218`. The same seed
gives the same 40 arrays.
**PP3.** Each array carries 12 values, ranging from −9 to 20.
**PP4.** The oracle is brute force and is counted as **always correct**. The pattern's
correctness is claimed only by comparison against the oracle.
**PP5.** The corpus satisfying the precondition is the **sorted** form of the same 40 arrays;
it comes from no other generator. The only difference between the two corpora is order.

```python
SEED, LENGTH, CORPUS_SIZE = 20260218, 12, 40


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def corpus(seed=SEED, n=CORPUS_SIZE, length=LENGTH):
    r = generator(seed)
    return [{"no": i + 1, "array": [r(30) - 9 for _ in range(length)]}
            for i in range(n)]


class Counter:
    def __init__(self):
        self.step = 0

    def count(self, n=1):
        self.step += n


def oracle_pairs(array, target, s):
    """Tries every pair. Always correct, always expensive."""
    for i in range(len(array)):
        for j in range(i + 1, len(array)):
            s.count()
            if array[i] + array[j] == target:
                return True
    return False


def pattern_two_pointers(array, target, s):
    """PRECONDITION: array must be sorted."""
    left, right = 0, len(array) - 1
    while left < right:
        s.count()
        t = array[left] + array[right]
        if t == target:
            return True
        if t < target:
            left += 1
        else:
            right -= 1
    return False


def measure(items, target):
    diverging, pk, ok = [], 0, 0
    for k in items:
        s1, s2 = Counter(), Counter()
        a = pattern_two_pointers(k["array"], target, s1)
        b = oracle_pairs(k["array"], target, s2)
        pk, ok = pk + s1.step, ok + s2.step
        if a != b:
            diverging.append(k["no"])
    return {"diverging": len(diverging), "first_diverging": diverging[:6],
            "pattern_step": pk, "oracle_step": ok, "ratio": round(ok / pk, 2)}


K = corpus()
S = [dict(k, array=sorted(k["array"])) for k in K]
print("corpus:", len(K), "arrays x", LENGTH, "values | already sorted:",
      sum(1 for k in K if k["array"] == sorted(k["array"])))
for ad, items in (("precondition holds", S), ("precondition broken", K)):
    print(f"  {ad}", measure(items, 11))
```

```
corpus: 40 arrays x 12 values | already sorted: 0
  precondition holds {'diverging': 0, 'first_diverging': [], 'pattern_step': 154, 'oracle_step': 972, 'ratio': 6.31}
  precondition broken {'diverging': 25, 'first_diverging': [1, 2, 3, 6, 8, 9], 'pattern_step': 372, 'oracle_step': 866, 'ratio': 2.33}
```

Three numbers sit side by side. When the precondition holds, the pattern gives the same
answer as the oracle on **40 of 40 inputs** and spends **154** steps; the oracle spends
**972**, a ratio of **6.31**. When the precondition breaks, diverging inputs come to **25**
and the ratio drops to **2.33**.

The most important part of the second row is not the diverging-input count, it is that the
two arrive together. **Wrongness is not cheap either:** the pattern's step count climbs from
154 to 372, because in an unsorted array the pointers meet at the ends before finding the
right pair and the pattern cannot exit early. As the speedup falls from 6.31 to 2.33 times,
correctness goes with it.

## What Happens on a Diverging Input

The divergence has a single cause. While applying the rule "if the sum is small, grow the
left value," the pattern assumes that **the left value grows moving rightward**. In an
unsorted array this assumption is false; once a pointer moves in the wrong direction, the
skipped positions are never revisited.

```python
def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def corpus(seed):
    r = generator(seed)
    return [[r(30) - 9 for _ in range(12)] for _ in range(40)]


def oracle_pairs(array, target):
    for i in range(len(array)):
        for j in range(i + 1, len(array)):
            if array[i] + array[j] == target:
                return True, (array[i], array[j])
    return False, None


def pattern_two_pointers(array, target):
    left, right = 0, len(array) - 1
    while left < right:
        t = array[left] + array[right]
        if t == target:
            return True
        if t < target:
            left += 1
        else:
            right -= 1
    return False


first = corpus(20260218)[0]
print("input 1 :", first)
print("  pattern:", pattern_two_pointers(first, 11))
print("  oracle :", oracle_pairs(first, 11))
print("  sorted :", sorted(first), "-> pattern", pattern_two_pointers(sorted(first), 11))
print()
print("seed       target  precondition   diverging/40")
for seed in (20260218, 20260219):
    for target in (11, 25):
        K = corpus(seed)
        for ad, items in (("holds     ", [sorted(d) for d in K]), ("broken    ", K)):
            diverging = sum(1 for d in items
                            if pattern_two_pointers(d, target) != oracle_pairs(d, target)[0])
            print(f"{seed}  {target:5d}  {ad}  {diverging:8d}"
                  f"    ratio {diverging / 40:.4f}")
```

```
input 1 : [-8, -5, 2, -1, 2, 5, 4, 1, 16, 17, 6, -1]
  pattern: False
  oracle : (True, (-5, 16))
  sorted : [-8, -5, -1, -1, 1, 2, 2, 4, 5, 6, 16, 17] -> pattern True

seed       target  precondition   diverging/40
20260218     11  holds              0    ratio 0.0000
20260218     11  broken            25    ratio 0.6250
20260218     25  holds              0    ratio 0.0000
20260218     25  broken            22    ratio 0.5500
20260219     11  holds              0    ratio 0.0000
20260219     11  broken            24    ratio 0.6000
20260219     25  holds              0    ratio 0.0000
20260219     25  broken            16    ratio 0.4000
```

On the first input, the oracle finds the pair `(-5, 16)`; the pattern returns `False`. Once
the same array is sorted, the pattern also returns `True`. **The input did not change, only
its order did** — what changes the pattern's answer is not the data's content but whether the
precondition holds.

**PP6.** The diverging-input count is out of 40. One divergence in 40 inputs is 0.0250; a
1-input gap **counts as unmeasured**, 3 and above is meaningful.
**PP7.** The second corpus comes from seed `20260219` and is used only to test whether the
ratio holds its **order of magnitude**.

In the second corpus, diverging inputs for target 11 are **24**, versus **25** in the first.
For target 25 they are **16** and **22**. In all four measurements the ratio falls between
0.40 and 0.63 — **the same order of magnitude**; the result does not depend on the corpus.
On all four rows where the precondition holds, diverging inputs are **zero**, and that too is
corpus-independent.

## The Cost of Establishing the Precondition

The measurement so far leaves a question open: if the array is not sorted, it **can be
sorted**. Then the pattern can still be used. But sorting itself spends steps, and those steps
must be charged to the pattern's account.

**PP8.** When measuring the cost of establishing the precondition, sorting is performed with
a **comparison-based** procedure and comparisons are counted as steps. The sorting procedures
themselves were measured in the Algorithms course; they are not repeated here, only their
step count is counted.

```python
def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def corpus(seed=20260218):
    r = generator(seed)
    return [[r(30) - 9 for _ in range(12)] for _ in range(40)]


class Counter:
    def __init__(self):
        self.step = 0

    def count(self):
        self.step += 1


def oracle_pairs(array, target, s):
    for i in range(len(array)):
        for j in range(i + 1, len(array)):
            s.count()
            if array[i] + array[j] == target:
                return True
    return False


def pattern_two_pointers(array, target, s):
    left, right = 0, len(array) - 1
    while left < right:
        s.count()
        t = array[left] + array[right]
        if t == target:
            return True
        if t < target:
            left += 1
        else:
            right -= 1
    return False


def sort_counting(array, s):
    """The cost of establishing the precondition. Comparisons are counted as steps."""
    a = list(array)
    for i in range(1, len(a)):
        j = i
        while j > 0:
            s.count()
            if a[j - 1] <= a[j]:
                break
            a[j - 1], a[j] = a[j], a[j - 1]
            j -= 1
    return a


print("target  correct  pattern only  sorting included  oracle  ratio")
for target in (11, 25):
    only, included, oracle, correct = 0, 0, 0, 0
    for array in corpus():
        sa, sk, sh = Counter(), Counter(), Counter()
        y = pattern_two_pointers(sort_counting(array, sa), target, sk)
        h = oracle_pairs(array, target, sh)
        only += sk.step
        included += sa.step + sk.step
        oracle += sh.step
        correct += (y == h)
    print(f"{target:5d}  {correct:2d}/40  {only:12d}  {included:14d}  {oracle:5d}"
          f"  {oracle / included:5.2f}")
```

```
target  correct  pattern only  sorting included  oracle  ratio
   11  40/40           154            1737    866   0.50
   25  40/40           352            1935   1564   0.81
```

Correctness comes back: **40/40**. But the ratio **drops below 1**. For target 11, total
steps including sorting are **1737**, the oracle spends **866**; the pattern does **twice**
the oracle's work. For target 25 it is 1935 against 1564, a ratio of 0.81.

This is the topic's second claim making its first payment: **a speedup sometimes does not
speed anything up.** At this input size, two pointers forced to establish its own
precondition is more expensive than brute force. The pattern wins where sorting is done
**once** and queried **many times**, or where the data already arrives sorted. As the array
grows this balance shifts — sorting grows as $n \log n$, the oracle as $n^2$ — but in this
corpus 12 values is small enough to leave the balance in brute force's favor.

## Step Count Says Nothing About Correctness

In the two measurements above, divergence arrived together with a step change: from 154 to
372. That is not a rule, and relying on it is dangerous. A counting form of the same pattern
shows this. The problem is now "how **many pairs** sum below the target"; the pattern uses
the fact that once a pair is counted at the right end, every pair in between is also counted.

**PP9.** In the counting form the pattern cannot exit early; in every run the pointers take
exactly n−1 steps. The step count is therefore independent of the input's content.

```python
def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def corpus(seed=20260218):
    r = generator(seed)
    return [[r(30) - 9 for _ in range(12)] for _ in range(40)]


class Counter:
    def __init__(self):
        self.step = 0

    def count(self):
        self.step += 1


def oracle_small_pairs(array, target, s):
    """Number of pairs summing below target. Every pair is tried."""
    count = 0
    for i in range(len(array)):
        for j in range(i + 1, len(array)):
            s.count()
            if array[i] + array[j] < target:
                count += 1
    return count


def pattern_small_pairs(array, target, s):
    """PRECONDITION: array must be sorted. Counting a pair at the right end counts the ones between it too."""
    left, right, count = 0, len(array) - 1, 0
    while left < right:
        s.count()
        if array[left] + array[right] < target:
            count += right - left
            left += 1
        else:
            right -= 1
    return count


print("precondition  diverging/40  pattern  oracle   ratio")
for ad, prepare in (("holds     ", sorted), ("broken    ", list)):
    diverging, pk, ok = 0, 0, 0
    for array in corpus():
        d = prepare(array)
        s1, s2 = Counter(), Counter()
        a = pattern_small_pairs(d, 6, s1)
        b = oracle_small_pairs(d, 6, s2)
        pk, ok = pk + s1.step, ok + s2.step
        diverging += (a != b)
    print(f"{ad}  {diverging:8d}  {pk:5d}  {ok:5d}  {ok / pk:5.2f}")
```

```
precondition  diverging/40  pattern  oracle   ratio
holds              0    440   2640   6.00
broken            39    440   2640   6.00
```

The step columns in both rows are **identical**: pattern 440, oracle 2640, ratio 6.00. The
diverging-input column climbs from 0 to **39** — on 39 of 40 inputs the pattern returns a
wrong number. The pattern still returns an integer, still six times faster, still produces no
warning.

This shows why the topic's third claim is necessary. Step count is a performance metric and
**says nothing about correctness**. Brute force here is not a "slow alternative," it is the
**only** tool that makes the 39 wrong answers visible. Without the oracle, these two rows
would be indistinguishable.

## Three Numbers

| Metric | Oracle | Pattern | Diverging input |
|---|---|---|---|
| Precondition holds (target 11) | 972 steps | 154 steps | **0/40** |
| Precondition broken (target 11) | 866 steps | 372 steps | **25/40** |
| Establishing the precondition (target 11) | 866 steps | 1737 steps | **0/40** |
| Counting form, precondition broken | 2640 steps | 440 steps | **39/40** |

Three rows are three separate decision points. The first row is the pattern's promise. The
second shows what happens when the precondition is not checked: sixty-two percent of the
answers are broken and the speedup has eroded by two thirds. The third row is the bill for
establishing the precondition by hand.

One might think the pattern can be made safe by adding a check: look at whether the array is
sorted, and fall back to the oracle if it is not. That check is n−1 comparisons, that is, 440
steps for 40 arrays. The check **rescues correctness** but does **not rescue the speedup**:
on unsorted input, the work still falls to the oracle. What needs to be measured is not the
check's cost but what share of inputs satisfy the precondition. In this corpus that number is
**zero**.

## Summary

- Choosing a pattern is accepting a precondition; two pointers' precondition is that the
  array be sorted.
- When the precondition holds, the pattern matches the oracle on 40 of 40 inputs and spends
  154 steps instead of 972; the ratio is 6.31.
- When the precondition breaks, the pattern diverges from the oracle on **25 inputs** and the
  speedup drops to 2.33 times; wrongness is not cheap.
- In the second corpus, diverging inputs are 24; because the ratio holds its order of
  magnitude, the result does not depend on the corpus.
- Establishing the precondition by sorting brings correctness back but raises total steps to
  1737, making the pattern more expensive than the oracle.

## Next Step

Two pointers squeezed the array from both ends and its precondition was order. The next
pattern keeps the pointers moving in the **same direction** and grows and shrinks the region
between them like a **window**; its gain comes from updating the sum incrementally instead of
recomputing it from zero each time it slides. Its precondition is also different and never
looks at order at all: **no value may be negative**. The next lesson will count the 10 inputs
where that precondition breaks, using the oracle.