Fast and Slow Pointer

The previous two patterns worked on an array: the length was known, every position was reachable through an index. This lesson’s structure is different. There is a starting node and every node has a successor; the length is unknown, there is no going back, and whether the structure has an end is not known in advance.

The pattern advances two pointers in the same direction but at different speeds: the slow one takes one step, the fast one takes two. Its precondition is one sentence: progress must be one-directional, that is, every node must have exactly one successor. This lesson counts the inputs where that precondition breaks and shows that the pattern’s real gain is not in steps but in the held node count.

Cycle Detection

The first problem is this: does a traversal starting from the beginning run forever. The oracle searches for a cycle with the Data Structures course’s depth-first search; the “visited” versus “still open” distinction there is not repeated, it is used directly. The pattern holds no set at all: two pointers advance at different speeds and, if a cycle exists, sooner or later meet at the same node.

PP18. The structure has 12 nodes; the nodes are laid out along a path, and the path’s end either terminates or loops back. Seed 20260218. PP19. The only thing that breaks the precondition is a second back edge added to some nodes. The corpus satisfying the precondition is the same structures with their second edges dropped. PP20. The pattern always follows the first successor; it cannot see whether a second edge exists, because the only thing it looks at is successor[d][0]. PP21. Alongside step count, a second metric is kept: the number of nodes held at once. For the oracle this is the largest size the visited set reaches; for the pattern it is two pointers.

SEED, NODES, 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 chain_corpus(seed=SEED, n=CORPUS_SIZE, nodes=NODES):
    """Every structure has a path. The path's end either terminates or loops back; a
    SECOND back edge is also added to some nodes."""
    r = generator(seed)
    items = []
    for i in range(n):
        path = list(range(nodes))
        for j in range(nodes - 1, 0, -1):
            k = r(j + 1)
            path[j], path[k] = path[k], path[j]
        successor = {path[j]: [path[j + 1]] for j in range(nodes - 1)}
        successor[path[-1]] = [path[r(nodes)]] if r(100) < 40 else [-1]
        if r(100) < 60:
            p = 2 + r(nodes - 3)
            successor[path[p]].append(path[r(p)])
        items.append({"no": i + 1, "start": path[0], "successor": successor})
    return items


def one_directional(successor):
    """Second edges are dropped: every node keeps exactly one successor."""
    return {d: [a[0]] for d, a in successor.items()}


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

    def count(self, held=0):
        self.step += 1
        self.held = max(self.held, held)


def oracle_cycle(start, successor, s):
    """Walks every edge. Depth-first search's cycle detection is used directly."""
    visited, open_set = set(), set()

    def visit(d):
        visited.add(d)
        open_set.add(d)
        s.count(len(visited))
        for k in successor.get(d, []):
            if k == -1:
                continue
            if k in open_set:
                return True
            if k not in visited and visit(k):
                return True
        open_set.discard(d)
        return False
    return visit(start)


def pattern_fast_slow(start, successor, s):
    """PRECONDITION: every node must have EXACTLY ONE successor. The pattern follows the first."""
    slow = fast = start
    while True:
        s.count(2)
        for _ in range(2):
            fast = successor[fast][0]
            if fast == -1:
                return False
        slow = successor[slow][0]
        if slow == fast:
            return True


def measure(items, one_way):
    diverging, pk, ok, hk, ho = [], 0, 0, 0, 0
    for k in items:
        successor = one_directional(k["successor"]) if one_way else k["successor"]
        s1, s2 = Counter(), Counter()
        a = pattern_fast_slow(k["start"], one_directional(k["successor"]), s1)
        b = oracle_cycle(k["start"], successor, s2)
        pk, ok = pk + s1.step, ok + s2.step
        hk, ho = max(hk, s1.held), max(ho, s2.held)
        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),
            "pattern_held": hk, "oracle_held": ho}


K = chain_corpus()
print("corpus:", len(K), "structures x", NODES, "nodes | with a second edge:",
      sum(1 for k in K if any(len(a) > 1 for a in k["successor"].values())))
for ad, one_way in (("precondition holds", True), ("precondition broken", False)):
    print(f"  {ad}", measure(K, one_way))

corpus: 40 structures x 12 nodes | with a second edge: 23
  precondition holds {'diverging': 0, 'first_diverging': [], 'pattern_step': 299, 'oracle_step': 480, 'ratio': 1.61, 'pattern_held': 2, 'oracle_held': 12}
  precondition broken {'diverging': 14, 'first_diverging': [2, 8, 11, 12, 16, 19], 'pattern_step': 299, 'oracle_step': 480, 'ratio': 1.61, 'pattern_held': 2, 'oracle_held': 12}

The step columns of both rows are identical: pattern 299, oracle 480, ratio 1.61. The held-node columns are the same too: pattern 2, oracle 12. The only column that changes is diverging input — from 0 to 14.

The step ratio of 1.61 is already modest, and it is not the pattern’s selling point either. The pattern wins on held node count: the oracle must hold every node of the structure in a set, the pattern holds nothing but two pointers. As the node count grows, what the oracle holds grows, while the pattern’s stays at 2. That is the measured gain, and it does not change at all when the precondition breaks — only the answer breaks.

Why the meeting is guaranteed also rests on the one-successor assumption. Once the two pointers enter a cycle, the distance between them shrinks by exactly one every turn, because the fast one takes two steps and the slow one takes one. The distance is an integer and takes one of a number of values equal to the cycle length; because it shrinks by one every turn, it reaches zero in a finite number of turns. A distance that shrinks by one means exactly one path leaves every node. With a second successor present, there is no such single number as “the distance between them,” and the argument collapses.

Why the Second Edge Stays Invisible

The pattern’s only source of information is the successor[d][0] value. If a node has a second successor, the pattern never queries it — it cannot, because the pattern’s definition is built on the “single successor” assumption. If a structure’s only closing cycle runs through the second edge, the pattern never enters that cycle and returns False.

def generator(seed):
    d = seed

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


def chain_corpus(seed, n=40, nodes=12):
    r = generator(seed)
    items = []
    for i in range(n):
        path = list(range(nodes))
        for j in range(nodes - 1, 0, -1):
            k = r(j + 1)
            path[j], path[k] = path[k], path[j]
        successor = {path[j]: [path[j + 1]] for j in range(nodes - 1)}
        successor[path[-1]] = [path[r(nodes)]] if r(100) < 40 else [-1]
        if r(100) < 60:
            p = 2 + r(nodes - 3)
            successor[path[p]].append(path[r(p)])
        items.append({"no": i + 1, "start": path[0], "successor": successor})
    return items


def one_directional(successor):
    return {d: [a[0]] for d, a in successor.items()}


def oracle_cycle(start, successor):
    visited, open_set = set(), set()

    def visit(d):
        visited.add(d)
        open_set.add(d)
        for k in successor.get(d, []):
            if k == -1:
                continue
            if k in open_set:
                return True
            if k not in visited and visit(k):
                return True
        open_set.discard(d)
        return False
    return visit(start)


def pattern_fast_slow(start, successor):
    slow = fast = start
    while True:
        for _ in range(2):
            fast = successor[fast][0]
            if fast == -1:
                return False
        slow = successor[slow][0]
        if slow == fast:
            return True


K = chain_corpus(20260218)
example = next(k for k in K
               if pattern_fast_slow(k["start"], one_directional(k["successor"]))
               != oracle_cycle(k["start"], k["successor"]))
print("first diverging input no:", example["no"], "| start:", example["start"])
print("  successor:", {d: a for d, a in sorted(example["successor"].items())})
print("  pattern (first successor):", pattern_fast_slow(example["start"], one_directional(example["successor"])))
print("  oracle (all edges):", oracle_cycle(example["start"], example["successor"]))
print()
print("seed       precondition   cyclic (oracle)  diverging/40   ratio")
for seed in (20260218, 20260219):
    K = chain_corpus(seed)
    for ad, one_way in (("holds     ", True), ("broken    ", False)):
        cyclic = diverging = 0
        for k in K:
            successor = one_directional(k["successor"]) if one_way else k["successor"]
            b = oracle_cycle(k["start"], successor)
            cyclic += b
            diverging += (pattern_fast_slow(k["start"], one_directional(k["successor"])) != b)
        print(f"{seed}  {ad}  {cyclic:15d}  {diverging:8d}   {diverging / 40:.4f}")

first diverging input no: 2 | start: 0
  successor: {0: [8], 1: [2], 2: [7], 3: [-1], 4: [1, 8], 5: [10], 6: [5], 7: [6], 8: [9], 9: [11], 10: [3], 11: [4]}
  pattern (first successor): False
  oracle (all edges): True

seed       precondition   cyclic (oracle)  diverging/40   ratio
20260218  holds                    16         0   0.0000
20260218  broken                   30        14   0.3500
20260219  holds                    18         0   0.0000
20260219  broken                   32        14   0.3500

In the second input, node 4 has two successors: 1 and 8. The pattern sees only 1 and follows the path 0 → 8 → 9 → 11 → 4 → 1 → 2 → 7 → 6 → 5 → 10 → 3 → end, saying False. The oracle also tries the 4 → 8 edge and finds the cycle 8 → 9 → 11 → 4.

PP22. The second corpus comes from seed 20260219. In both corpora, diverging inputs are 14/40, ratio 0.3500; the result does not depend on the corpus.

The Middle Element and Not Stopping

The second problem is the same pattern’s most commonly used second form: finding the structure’s middle node. The oracle collects the nodes in order, then picks the middle one — two passes and a collection. The pattern finishes in a single pass: when the fast pointer reaches the end, the slow pointer is in the middle.

Here the precondition changes. The middle element is only defined if the structure has an end; if there is a cycle, there is no such node as “the middle.” The oracle sees this and returns undefined. There is nothing for the pattern to see: the fast pointer spins forever inside the cycle.

PP23. In this measurement there are no second edges; the structures are single-successor. The precondition that breaks is acyclicity. PP24. The pattern is given a step cap (48 steps). A run that hits the cap returns did not stop and is counted as diverging from the oracle. Without the cap the measurement would never finish.

def generator(seed):
    d = seed

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


def path_corpus(seed=20260218, n=40, nodes=12):
    """`end` is the path's last node; a back link from there means the structure has a cycle."""
    r = generator(seed)
    items = []
    for i in range(n):
        path = list(range(nodes))
        for j in range(nodes - 1, 0, -1):
            k = r(j + 1)
            path[j], path[k] = path[k], path[j]
        successor = {path[j]: path[j + 1] for j in range(nodes - 1)}
        successor[path[-1]] = path[r(nodes)] if r(100) < 40 else -1
        r(100)
        items.append({"no": i + 1, "start": path[0], "end": path[-1], "successor": successor})
    return items


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

    def count(self, held=0):
        self.step += 1
        self.held = max(self.held, held)


def oracle_middle(start, successor, s):
    """First collects every node, then picks the middle one. Holds a visited set."""
    visited, order, d = set(), [], start
    while d != -1 and d not in visited:
        visited.add(d)
        order.append(d)
        s.count(len(visited))
        d = successor[d]
    if d != -1:
        return "undefined"
    for _ in range(len(order) // 2 + 1):
        s.count(len(visited))
    return order[len(order) // 2]


def pattern_middle(start, successor, s, cap=48):
    """PRECONDITION: structure must not contain a cycle. Single pass, holds only two pointers."""
    slow = fast = start
    while True:
        s.count(2)
        if s.step > cap:
            return "did not stop"
        if fast == -1 or successor[fast] == -1:
            return slow
        fast = successor[successor[fast]]
        slow = successor[slow]


K = path_corpus()
A = [dict(k, successor={**k["successor"], k["end"]: -1}) for k in K]
print("corpus:", len(K), "structures | with a cycle:",
      sum(1 for k in K if k["successor"][k["end"]] != -1))
print("precondition  diverging/40  pattern  oracle   ratio  pattern held  oracle held")
for ad, items in (("holds     ", A), ("broken    ", K)):
    diverging, pk, ok, hk, ho = 0, 0, 0, 0, 0
    for k in items:
        s1, s2 = Counter(), Counter()
        a = pattern_middle(k["start"], k["successor"], s1)
        b = oracle_middle(k["start"], k["successor"], s2)
        pk, ok = pk + s1.step, ok + s2.step
        hk, ho = max(hk, s1.held), max(ho, s2.held)
        diverging += (a != b)
    print(f"{ad}  {diverging:8d}  {pk:5d}  {ok:5d}  {ok / pk:5.2f}"
          f"  {hk:13d}  {ho:13d}")

corpus: 40 structures | with a cycle: 14
precondition  diverging/40  pattern  oracle   ratio  pattern held  oracle held
holds              0    280    760   2.71              2             12
broken            14    868    662   0.76              2             12

When the precondition holds, the pattern finds the same node as the oracle on 40 of 40 inputs at 280 steps; the oracle spends 760, a ratio of 2.71. Once cyclic structures arrive, diverging inputs come to 14 and the ratio drops to 0.76 — the pattern becomes more expensive than the oracle.

This row shows something the previous two lessons did not. There, when the precondition broke, the pattern gave a wrong answer and finished in a normal step count. Here the pattern does not finish: most of the 868 steps are pointers spinning until they hit the cap in each of the fourteen structures. Without a cap, the measurement would never have completed. The precondition’s cost is not always a wrong answer; sometimes it is no answer at all.

Three Numbers

Metric	Oracle	Pattern	Diverging input
Cycle detection, precondition holds	480 steps / 12 nodes	299 steps / 2 nodes	0/40
Cycle detection, with a second edge	480 steps / 12 nodes	299 steps / 2 nodes	14/40
Middle element, precondition holds	760 steps / 12 nodes	280 steps / 2 nodes	0/40
Middle element, cyclic structure	662 steps / 12 nodes	868 steps / 2 nodes	14/40

In all four rows the pattern’s held node count is 2, the oracle’s is 12. This column explains why the pattern exists, and it never changes across the four rows. The diverging input column is zero twice and fourteen twice — reading the other columns without reading that one means missing that the pattern gives a wrong answer on fourteen inputs.

Summary

• Fast and slow pointer finds a cycle and the middle node in a one-directional structure of unknown length, holding no set at all.
• The precondition is that every node have exactly one successor; once a second edge is added, the pattern never queries it and diverges from the oracle on 14 inputs.
• The divergence is not reflected in step count: on both corpora the pattern spends 299 steps and the oracle spends 480.
• The pattern’s measured gain is not in steps but in held node count: 2 versus 12, and this ratio stays fixed even when the precondition breaks.
• In the middle-element problem the precondition is acyclicity; on a cyclic structure the pattern does not just give a wrong answer, it hits the step cap and the ratio drops from 2.71 to 0.76.

Next Step

The three patterns so far worked in a single pass over a single structure. The next pattern first rearranges the input: merging overlapping intervals begins by sorting the intervals by some criterion. The precondition is no longer a property of the data but the criterion itself — and sorting by the wrong criterion breaks the pattern. The next lesson compares three separate sorting criteria against the same oracle and counts how many inputs each merges wrongly.