Why does following i to a[i] in an array whose values are all valid indices guarantee a loop?

## The scenario An audit runs over a shipment manifest: a fixed table where every slot holds a slot number, drawn from a range that is always valid for the table. The manifest is a shared read-only snapshot — other jobs are reading it concurrently, so you may not sort it, may not reorder it, and may not scribble markers into it. You also have a tight memory allowance because the audit runs alongside everything else. On its face this is a table of numbers. The recognition step is seeing that it is a chain. ## Values that are valid indices are pointers Stop reading `a[i]` as "the number stored at position `i`" and start reading it as "**the successor of position `i`**". The step function is `f(i) = a[i]`. Nothing else changes; the same bytes now describe a graph whose nodes are the positions. Two properties of that graph decide everything: - **Out-degree is exactly one.** Every slot holds precisely one number, and that number is a valid position. So every node has exactly one outgoing edge — no branching, no dead ends. This is a *functional graph*, which is the structure the fast/slow pattern requires. - **The node set is finite.** There are only as many positions as the table has slots. Total step plus finite domain means the walk from any start cannot terminate and cannot produce new positions forever. Pigeonhole forces a position to recur, and because the successor depends only on the current position, everything after the recurrence replays with a fixed period. The walk therefore has the standard shape: a tail traversed once, feeding a loop traversed forever. Notice that the guarantee comes from the *range constraint on the values*, not from anything about the numbers themselves. That is the entire recognition leap, and it is why the interviewer's phrasing always insists that every entry is in range. ## Why repeated values become merge points Here is the structural fact that makes this modelling useful rather than merely cute. A node's **in-degree** is how many slots store that node's number. In a functional graph, the place where the tail joins the loop is a node reached from two different predecessors — one on the tail, one on the loop — so it has in-degree at least two. And in-degree at least two means *two distinct slots hold the same number*. So a duplicated value in the data is not merely a fact about the numbers; it is precisely what creates a merge in the walk. Conversely, if every value were distinct and in range, the graph would be a permutation: every node with in-degree exactly one, every walk a pure loop with no tail at all. The presence of a tail is the signature of a duplicate. One subtlety completes the argument. For the loop's entry point to be a merge, the walk must *start outside the loop*. If you begin at a node that no slot points to — a node with in-degree zero — you are guaranteed to be on a tail, so the first loop node you reach genuinely has two predecessors. Beginning at an arbitrary position gives no such guarantee; you might start inside the loop, walk a pure cycle, and learn nothing about merges. Choosing a start with no incoming edge is a real precondition, not a formality. Detecting that the walk loops is the first half of the work. Recovering exactly which node the tail merges into is a separate phase with its own argument, and it is a mistake to claim the detection alone hands it to you. ## Why the constraints in the scenario force this view The obvious approaches all collide with the stated constraints: - **Sort and scan for adjacent equals** — mutates the shared snapshot, and costs `n log n` besides. - **Copy, then sort** — buys back correctness by spending linear memory, exactly what the allowance forbids. - **Mark visited slots in place**, for example by flipping a sign or setting a high bit — mutates a snapshot other readers depend on, and corrupts the values it borrows bits from. - **Record visited positions in a membership structure** — correct and simple, but linear memory again. The pointer-following view survives all four constraints because it stores two positions and writes nothing. When an interviewer stacks "read-only" and "constant extra space" onto array data whose values are in index range, that pairing is the tell: they are asking you to see the implicit chain. ## What breaks the model - **An out-of-range value** makes the step partial: the walk can run off the table, out-degree is no longer one everywhere, and the loop guarantee dies. You would need an explicit termination check, and the answer changes. - **An empty or missing slot** is the same failure in different clothing — a node with no outgoing edge. - **A slot holding a set of successors** turns the functional graph into a general one, where two racing pointers prove nothing. - **A table being written concurrently** destroys determinism: the same position can yield different successors on two visits, so the two pointers are no longer walking the same sequence. The read-only snapshot is not a convenience in this scenario; it is a correctness requirement. ## The transferable idea Any time a value is *constrained to name another element of the same finite collection*, you have an implicit functional graph and every cycle technique becomes available — with no list, no links, and no allocation. Recognising that framing on unfamiliar data is worth far more in an interview than memorising any particular walk.