---
title: 'Fast and Slow Pointer'
source: 'https://academia.sh/en/courses/advanced-algorithms/fast-and-slow-pointer'
course: 'Advanced Algorithms and Problem Solving'
language: en
updated: '2026-08-17T18:07:29+00:00'
license: 'CC BY-SA 4.0'
---

# Fast and Slow Pointer

Cycle detection and the middle element using two pointers moving at different speeds; the 14 cycles a second edge makes invisible and the cost of never stopping.

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.

```python
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`.

```python
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.

```python
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.