Two Pointers

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.

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.

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.

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.

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.