When an array is secretly a linked list

If a value can be read as an index, an array becomes a list, and cycle detection applies to it.

Key idea

The reframe

An array whose values are all valid indexes into itself defines a walk: stand at index i, and the next index is the value stored there. That is exactly a linked list, with no nodes allocated anywhere.

Since the walk never leaves the array and the array is finite, it must eventually revisit a position. So this implicit list always contains a cycle, and the tools from the fast-and-slow lesson apply unchanged.

1values = [1, 3, 4, 2, 2]2 3position = 04visited = []5for _ in range(8):6    visited.append(position)7    position = values[position]8print(visited)

Why it works

Finding where the cycle begins

Detecting a cycle is the easy half. Finding its entrance needs a second phase, and the fact behind it is worth stating precisely.

Let the distance from the start to the cycle entrance be a, and let the meeting point of the two pointers sit b steps into the cycle. When they meet, the fast pointer has traveled exactly twice as far as the slow one, and working that equality through shows that a equals the distance from the meeting point back around to the entrance.

So: after they meet, move one pointer back to the start and advance both one step at a time. They meet again exactly at the entrance.

The first phase is the same loop from three lessons ago, reading values[i] where you previously read node.next. Here it is on the array above, printing where the two pointers stand after each step.

1values = [1, 3, 4, 2, 2]2 3slow = fast = 04step = 05while True:6    slow = values[slow]7    fast = values[values[fast]]8    step += 19    print(f"step {step}: slow={slow}, fast={fast}")10    if slow == fast:11        break

They meet at index 4, which is inside the cycle but is not where it begins.

Why this problem is in a linked list unit

It has no linked list in it. It is here because the technique is the one from three lessons ago, and the entire difficulty is noticing that the array can be read as one.

That noticing is the skill worth having. When a problem forbids modifying the input and forbids extra space, and involves values that happen to be valid indexes, this reframe is what is being asked for.

Quick check· 5 min

Why must a cycle exist?

In an array of length n whose values are all valid indexes, why is the walk guaranteed to cycle?

The walk never leaves the array and there are finitely many positions, so some position must repeat, and from there the walk repeats foreverBecause the array is guaranteed to contain a duplicate valueBecause every value is smaller than the array lengthIt is not guaranteed; the walk can reach a position with no successor

Problem· 30 min

Find The Duplicate Number

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1values = [1, 3, 4, 2, 2]2 3slow = fast = 04step = 05while True:6 slow = values[slow]7 fast = values[values[fast]]8 step += 19 print(f"step {step}: slow={slow}, fast={fast}")10 if slow == fast:11 break

Why this problem is in a linked list unit

It has no linked list in it. It is here because the technique is the one from three lessons ago, and the entire difficulty is noticing that the array can be read as one.