Cycle Detection in Implicit Sequences

## The setting Picture a workflow engine for deployments. Every stage — build, canary, soak, promote, roll back — has exactly one outgoing transition determined by the stage's own recorded outcome. A deployment has been sitting in the pipeline for six hours and someone asks: is it making progress, or is it looping between roll-back and re-canary forever? There is no list to walk. There are no next-pointers, no array, no stored path. There is a current stage identifier and a rule that computes the next one. That rule is the **step function** `f`, and the walk `s, f(s), f(f(s)), ...` is an implicit sequence. Two pointers moving at different speeds over it can answer the looping question in constant space — but only if `f` satisfies a short list of properties, and knowing that list is the difference between recognising the pattern and misapplying it. ## Requirement 1: deterministic and free of side effects The faster pointer advances two steps for every one the slower takes, which means the step function is invoked on the same value that the slow pointer will later reach. If `f` consults a random source, a clock, a mutable counter, or the path taken so far, the two pointers are no longer walking *the same* sequence, and equality between them means nothing. Side effects are the same problem wearing a different hat. If evaluating `f` advances a cursor, consumes from a stream, writes an audit row, or mutates the state it was asked about, then evaluating it three times per element — which this pattern does — corrupts the very thing being examined. The step must be a pure query, safe to call again on the same input and get the same answer. ## Requirement 2: exactly one successor — a functional graph This is the requirement candidates skip, and it is the one that decides whether the pattern applies at all. Draw every reachable state as a node with an arrow to its successor. If each node has exactly **one** outgoing arrow, the structure is a *functional graph*: from any start there is a single path, and that path is precisely a chain. Two pointers can race along it because there is only one road. If some state can transition to either of two successors depending on an external signal, there is no single path — there is a branching structure with many walks, and "the fast pointer met the slow pointer" tells you nothing about whether any particular walk loops. That situation needs a traversal-based technique instead, and it is a genuinely different problem. So before reaching for two pointers, verify the modelling claim: *one state in, exactly one state out*. ## Requirement 3: the walk never simply ends Consider this fragment, which is the pattern in its bare form: ``` slow = start fast = start while true: slow = f(slow) fast = f(f(fast)) if slow == fast: return "cycle" ``` It has no exit other than finding a cycle. That is correct only when `f` is **total** on the reachable set — every state genuinely has a successor. In the deployment engine, a terminal stage such as "promoted" has no next transition. If the walk can end, the fragment is wrong as written: the loop must test whether `fast` or its successor is terminal *before* advancing and return "no cycle" there. Notice the asymmetry — the fast pointer reaches a terminal state first, so it alone needs the guard, and it needs it after both of its two hops. ## Requirement 4: a finite reachable set, and a cheap step Finiteness is what upgrades "a cycle might exist" to "a cycle is guaranteed unless the walk terminates", and it also bounds the running time: with a tail of `μ` steps and a cycle of `λ`, the pointers meet within about `μ + λ` iterations, so the work is linear in the number of distinct states reached, with constant extra memory. Cost matters because the pattern trades evaluations for memory. Each iteration performs three applications of `f` — one for the slow pointer, two for the fast — so roughly three times the step work of a single straightforward pass, and it caches nothing. When `f` is arithmetic or an array read, that is free. When `f` means a remote lookup or a database round trip, tripling it is a real bill, and recording visited states instead may be the better trade. ## What the technique gives you, and what it does not A meeting of the two pointers proves a cycle exists, in `O(1)` extra space. It does not by itself tell you which states form the loop, how long the loop is, or where the tail joins it — those come from separate follow-up phases. And it never gives you the visited path, so it cannot answer "show me the stages this deployment bounced between" without additional work. Knowing the boundary of what the meeting proves is exactly what stops a candidate from over-claiming in an interview. ## Recognising the pattern in the wild The cue is not the word "list". It is: *deterministic single-successor transition, bounded state space, no end marker, and a memory ceiling*. When those four line up, an implicit chain is hiding in the problem no matter what the domain looks like on the surface.