When is a visited-set loop check the right call over constant-space fast/slow pointers?

## Two answers to the same question Given a deterministic walk `x, f(x), f(f(x)), ...` with no end marker, there are two standard ways to decide whether it loops. **Record what you have seen.** Keep a membership structure of visited states; before each step, check whether the current state is already in it. A hit means a loop, and the state you hit is the first one that repeats. This costs `O(n)` space in the number of distinct states reached and evaluates the step once per state. **Race two pointers.** Advance one pointer one step and another two steps per iteration until they hold the same state. This costs `O(1)` space and evaluates the step about three times per element. Both are linear in time. Choosing between them is not a complexity question at all — the asymptotics on time match — it is a question about **memory, recomputation and what you need to learn**. ## What the set gives you that pointers do not 1. **The identity of the loop.** A membership hit is the first repeated state, immediately. The pointers' meeting point is just some state inside the loop, and turning that into "here is where the tail joins" or "here are the states in the loop" requires further phases you have to write and justify. 2. **The path, for a human.** In a stuck-deployment investigation the useful artefact is "this job bounced between roll-back and re-canary eleven times". The set already holds that history; the constant-space walk has thrown it away by construction. 3. **One evaluation per transition.** If computing the next state means a remote call, a signed lookup, or a costly derivation, the set lets you pay once per state. The pointer race recomputes: about three times the step work, deliberately, because it refuses to store anything. 4. **Tolerance of a partially defined step.** Recording states as you go composes naturally with early exits, retries and terminal states; the pointer loop needs careful guards for the fast pointer at every hop. ## What pointers give you that the set does not 1. **Flat memory.** A billion reachable states, even at a handful of bytes each plus structure overhead, is many gigabytes of resident memory — for one check. Two pointers hold two states, full stop. On a fleet of workers with a fixed memory budget per process, that is the whole argument. 2. **No hashing pathology.** Membership in a hash-based set is `O(1)` *expected*, not guaranteed; keys that collide heavily — sometimes adversarially chosen, sometimes just structurally similar identifiers — degrade lookups toward linear scans of a bucket, and the check that was supposed to be cheap becomes the hot spot. The pointer race performs equality comparisons only. 3. **Read-only, unannotatable input.** A common trick for the set-free version is to mark states as visited in place. When the data is a shared, read-only snapshot — an audit manifest others are reading concurrently, a memory-mapped region, a caller's buffer you promised not to touch — marking is off the table, and the pointer race is the technique that needs neither extra memory nor mutation. 4. **Unbounded or unknown state counts.** If you cannot bound the reachable set in advance, a set-based check is a memory risk with no ceiling; you would have to cap it and give up correctness. The pointer race has no such failure mode. ## The decision, stated as a rule Ask three questions in order: | Question | If yes | If no | | --- | --- | --- | | Do I need to *name* the looping states or show the path? | Set | continue | | Is one evaluation of the step much more expensive than the equality checks? | Set (or a memoised walk) | continue | | Can the reachable state count exceed my memory budget, or is the input read-only? | Two pointers | Either; take the simpler code | That last cell is worth saying out loud in an interview: when the state space is genuinely small and bounded — a few thousand workflow stages — the set is *better engineering*. It is shorter, obviously correct on inspection, easy to extend with the diagnostic, and its memory cost is a rounding error. Reaching for the clever constant-space walk there is optimisation without a constraint, and the next person to read the code pays for it. ## A middle option worth knowing An approximate membership filter uses a small fixed amount of memory for a very large state count, at the cost of false positives. Note the direction of the error carefully: such a filter can claim a state was seen when it was not, so it can report a loop that does not exist — never miss one that does. That makes it usable as a cheap **pre-filter** that triggers an exact confirmation pass, and unusable as the final word on its own. Getting that direction backwards is a common and expensive mistake. ## The framing that impresses The strong answer does not say "two pointers, because `O(1)` space is better". It says: the two techniques cost the same asymptotic time, so the choice is memory versus recomputation versus information, and here is which of those is actually scarce in this system.