Here is one of the most satisfying problems in all of computer science. The setup is deceptively simple. You are given an array of n+1 integers, and every single value in the array is between 1 and n, inclusive. Your task: find the duplicate number. That is it. One number appears at least twice. Find it.

Before you reach for your usual tools, read the constraints carefully, because they are what make this problem sing. First: you cannot modify the array. No sorting. The input must remain exactly as it was given to you. Second: you are allowed only O(1) extra space. No hash sets, no visited arrays, no auxiliary data structures that grow with the input. Third: you need better than O(n^2) time. No comparing every pair of elements.

Let that sink in. Sorting would find the duplicate in O(n log n) time -- you would just scan for adjacent equal elements -- but sorting mutates the array, and the problem forbids that. A hash set would find it in O(n) time and a single pass, but a hash set uses O(n) space, violating the space constraint. And the brute-force approach of checking every pair satisfies both the space and immutability constraints but runs in O(n^2) time, which is too slow.

Every standard approach fails on at least one constraint. That is not an accident. The problem is designed to make your standard toolkit useless. It is engineering a dead end.

But here is the thing about dead ends: they are only dead if you keep walking in the same direction. Every strategy you are about to try treats the array values as data -- numbers to be compared, sorted, or counted. What if that entire framing is wrong? What if the values are not data at all, but something else entirely?

There is a mathematical reason the duplicate must exist, and it is worth understanding deeply. It is called the pigeonhole principle, and it is one of the simplest yet most powerful ideas in discrete mathematics. The principle says: if you have n+1 items and only n containers, then at least one container must hold more than one item. There is no way around it. You cannot fit 6 objects into 5 boxes without at least one box containing two.

In our problem, the “items” are the n+1 array positions, and the “containers” are the n possible values (1 through n). Since there are more positions than values, at least one value must appear in more than one position. The duplicate is not just likely -- it is mathematically guaranteed. This is not a search problem where the target might not exist. The target always exists. The question is how to find it without violating the constraints.

Try each approach below. You are not looking for a solution yet. You are looking for the shape of the problem -- and these failures are the shape. Feel the wall. Every standard technique breaks. The breakthrough will come from changing what you think the numbers mean.

Every approach you just tried treats the array values as data -- numbers to be compared, sorted, or hashed. But what if you stopped thinking of them as data and started thinking of them as addresses?

Let us build this idea from absolute scratch with a concrete example. Take this array:

[2, 6, 4, 1, 3, 1, 2, 5]

This array has 8 elements, so the indices run from 0 to 7, and every value is between 1 and 7. Now, here is the key reinterpretation. Instead of reading arr[0] = 2 as “the first element is the number two,” read it as "index 0 points to index 2." The value is not a number to be compared. It is an address. A destination. A pointer.

Follow the chain. Start at index 0. The value there is 2, so you jump to index 2. Look at index 2: the value is 4, so you jump to index 4. Index 4 holds 3, so you jump to index 3. Index 3 holds 1, so you jump to index 1. Index 1 holds 6, so you jump to index 6. Index 6 holds 2, so you jump to index 2.

Stop. You have been to index 2 before. You just completed the chain: 0 ⟶ 2 ⟶ 4 ⟶ 3 ⟶ 1 ⟶ 6 ⟶ 2. The chain looped back on itself.

This is the f(i) = arr[i] mental model. The array defines a function: give it an index, and it hands you back a new index. That function is not abstract -- it is literally the array lookup. arr[0] gives you 2. arr[2] gives you 4. arr[4] gives you 3. Each cell contains the address of the next cell in the chain. Each position in the array is a node, and each value is a directed edge to another node.

You are no longer looking at an array. You are looking at a directed graph where every node has exactly one outgoing edge.

There is a critical structural observation here. The values in the array are in the range [1, n], meaning they can be 1, 2, 3, ..., 7 but never 0. That means no value in the array can ever point back to index 0. Index 0 is like the head of a linked list -- it can point outward, but nothing points to it. It is always the start of the chain, never a destination. This is important because it means the chain from index 0 is special: it begins at a node that can only be visited once (at the very start), and then proceeds into the rest of the graph.

Every other index in the range [1, n] can be a destination. In fact, since there are n+1 values (one per array position) mapping into only n possible destinations, the pigeonhole principle guarantees that at least one destination index is the target of two different source positions. Two arrows converge on the same node. That convergence is the duplicate. And that convergence is what creates the loop you just saw.

Follow the chain below. At each step, read the value and jump to that index. Watch how a flat array transforms into a graph with a cycle.

You just traced a chain through an array and watched it loop back to a node it had already visited. Now let us understand why this must always happen -- not just in this particular array, but in every array that satisfies the problem constraints. The reasoning is precise, and it rests on the pigeonhole principle applied in a specific way.

Here is the setup. You have an array of n+1 elements. The indices run from 0 to n. The values are in the range [1, n]. The function f(i) = arr[i] maps each index to a value, and since every value is a valid index (it is between 1 and n), you can follow the function indefinitely: start at some index, look up its value, go to that index, look up its value, go to that index, and so on.

Now, start the chain at index 0. The first step takes you to arr[0], which is some index in [1, n]. The second step takes you to arr[arr[0]], also in [1, n]. Every subsequent step lands on an index in the range [1, n]. But there are only n indices in that range. If you take n+1 steps, you will have visited n+1 indices from a set of only n possibilities. By the pigeonhole principle, at least one index must have been visited twice. The chain must revisit a node. There is no escape.

When the chain revisits a node, it means you have found a cycle. The chain from index 0 walks along a tail -- a sequence of nodes visited for the first time -- and then enters a cycle where nodes repeat forever. The resulting shape, if you draw it, looks like the Greek letter rho: a straight tail feeding into a closed loop. This shape has a name: the rho (ρ).

But here is the truly remarkable part. Think about what it means for a node to be the first revisited node -- the cycle entry. If the chain enters a cycle at some index k, it means that at some earlier point in the chain, the chain arrived at k for the first time. And now, at some later point, the chain has arrived at k again. How? Because some index j has arr[j] = k, and j is different from the index that first led to k. In other words, two different source indices -- let us call them i and j -- both have arr[i] = k and arr[j] = k. They both point to k. And that means k is a value that appears at least twice in the array.

The cycle entry IS the duplicate. Finding where the cycle starts is the same thing as finding the repeated number.

This is the core insight of the entire module. The array, interpreted through the lens of f(i) = arr[i], is a directed graph. The pigeonhole principle guarantees that graph contains a cycle. The cycle entry is the duplicate value. Three separate ideas -- arrays as graphs, pigeonhole cycles, and duplicate detection -- are actually the same idea viewed from three different angles.

You are about to build this shape with your own hands. The array from the previous screens is shown below. For each cell, draw the arrow it describes: read arr[i], then tap the cell at that index. Watch the array transform into a directed graph before your eyes, and watch the rho emerge.

Look at the shape you just built: a tail of nodes leading into a cycle. You have seen this exact structure before -- in linked lists. A linked list with a cycle has the same rho shape. A sequence of unique nodes forms the tail, then the list enters a loop and repeats forever. You already know an algorithm that finds the cycle entry in a linked list: Floyd's tortoise and hare.

The translation from linked lists to arrays is mechanical. In a linked list, “advance one step” means slow = slow.next. In the array, there is no .next pointer -- but there is arr[slow]. The value at index slow is the pointer to the next node. So “advance one step” becomes slow = arr[slow]. In a linked list, “advance two steps” means fast = fast.next.next -- follow two pointers in sequence. In the array, that becomes fast = arr[arr[fast]] -- look up the value at index fast to get an intermediate index, then look up the value at that index.

Let us walk through both phases on the concrete array [1, 3, 4, 2, 2].

Phase 1: The Chase. Both pointers start at index 0. The slow pointer moves one step per iteration: slow = arr[slow]. The fast pointer moves two steps: fast = arr[arr[fast]]. Because the fast pointer moves at twice the speed, once both pointers are inside the cycle, the fast pointer gains one position per iteration relative to the slow pointer. Eventually, it laps the slow pointer and they collide at the same index. This collision tells you nothing about which index is the duplicate -- it only proves that a cycle exists and gives you a meeting point inside it.

Concretely: Step 1, slow goes from 0 to arr[0] = 1, fast goes from 0 to arr[arr[0]] = arr[1] = 3. Step 2, slow goes to arr[1] = 3, fast goes to arr[arr[3]] = arr[2] = 4. Step 3, slow goes to arr[3] = 2, fast goes to arr[arr[4]] = arr[2] = 4. Step 4, slow goes to arr[2] = 4, fast goes to arr[arr[4]] = arr[2] = 4. Collision at index 4.

Phase 2: The Convergence. Move one pointer back to the start (index 0) and leave the other at the collision point (index 4). Now both pointers advance at the same speed -- one step at a time. The mathematical guarantee is this: the distance from the start to the cycle entry equals the distance from the collision point to the cycle entry (modulo the cycle length). So both pointers will arrive at the cycle entry at the exact same time.

Step 1: head goes to arr[0] = 1, pointer goes to arr[4] = 2. Step 2: head goes to arr[1] = 3, pointer goes to arr[2] = 4. Step 3: head goes to arr[3] = 2, pointer goes to arr[4] = 2. They meet at index 2. The value at index 2 is 2. The duplicate is 2.

O(n) time. O(1) space. No sorting. No hash set. No mutation. Just two pointers following f(i) = arr[i], the same algorithm you learned for linked lists, applied to a completely different data structure.

Step through the algorithm below and watch the chase and convergence unfold.

The rho shape does not only appear in arrays. It appears anywhere a function maps a finite set back to itself -- even when the function has nothing to do with arrays or linked lists or pointers. To see this, let us leave arrays behind entirely and enter a completely different domain: the “happy number” problem.

Here is the problem. Take any positive integer. Compute a new number by squaring each of its digits and adding the results. That gives you a new number. Repeat the process on the new number. Keep going. The question: does this sequence eventually reach 1, or does it cycle forever?

Let us work through two examples in full detail.

Example 1: n = 19. The digits of 19 are 1 and 9. Square each: 1^2 = 1, 9^2 = 81. Add: 1 + 81 = 82. Now take 82. Digits: 8 and 2. Squares: 64 and 4. Sum: 68. Take 68. Digits: 6 and 8. Squares: 36 and 64. Sum: 100. Take 100. Digits: 1, 0, 0. Squares: 1, 0, 0. Sum: 1. The sequence is 19 ⟶ 82 ⟶ 68 ⟶ 100 ⟶ 1.

What happens at 1? The digits of 1 are just “1.” The square is 1. The sum is 1. So f(1) = 1. The function maps 1 to itself. This is called a fixed point -- a cycle of length 1. The sequence terminates. Numbers that reach 1 are called happy numbers.

Example 2: n = 4. The digit of 4 is 4. Square: 16. Take 16. Digits: 1 and 6. Squares: 1 and 36. Sum: 37. Take 37. Squares: 9 and 49. Sum: 58. Take 58. Squares: 25 and 64. Sum: 89. Take 89. Squares: 64 and 81. Sum: 145. Take 145. Squares: 1, 16, 25. Sum: 42. Take 42. Squares: 16 and 4. Sum: 20. Take 20. Squares: 4 and 0. Sum: 4.

The sequence is 4 ⟶ 16 ⟶ 37 ⟶ 58 ⟶ 89 ⟶ 145 ⟶ 42 ⟶ 20 ⟶ 4. It returned to 4. The sequence is trapped in a cycle of length 8. It will never reach 1.

Why must every sequence either reach 1 or cycle? Because the digit-square-sum function has bounded output. Consider: a 3-digit number has digits at most 9, so the maximum output is 3 * 81 = 243. A 4-digit number (up to 9999) produces at most 4 * 81 = 324. Any number above 324 maps to something smaller than itself. This means that after a few iterations, every sequence enters the range 1324 and stays there. With only 324 possible values in that range, the pigeonhole principle kicks in: after 325 steps, some value must repeat. The sequence either settles on 1 (a fixed point) or enters a cycle.

This is the exact same structure as the array problem. The function f(n) = sum of squared digits maps positive integers to positive integers. The output is bounded. Finiteness guarantees a revisit. The sequence forms a rho shape: a tail leading into a cycle (or into the fixed point 1). And you can detect which case you are in -- cycle or fixed point -- using Floyd's algorithm. Same two pointers. Same collision logic. No hash set needed. No history stored. O(1) space.

Build both sequences below and watch the rho shapes emerge.

Let us zoom out as far as we can go. Forget arrays. Forget digit sequences. Consider any function f: S → S that maps a finite set to itself. Every element in S has exactly one image under f, which means every node in the directed graph of f has exactly one outgoing edge. What shapes can these graphs take?

The answer depends entirely on whether the function has collisions -- cases where two different inputs produce the same output.

Case 1: The function is a bijection. A bijection is a function where every output has exactly one input. No two different values of x produce the same f(x). In graph terms, every node has exactly one outgoing edge and exactly one incoming edge. No node receives two arrows, and no node is an “orphan” with zero incoming edges. The only graph structure that satisfies this is a collection of disjoint cycles. Every element participates in exactly one cycle. There are no tails at all.

Think about why. If every node has one edge in and one edge out, you can start at any node and follow edges forward. Eventually you must return to your starting node (pigeonhole). And since no node has two incoming edges, no “extra” path can join the cycle from outside. There is nothing outside the cycle -- every node is in one.

Consider f(x) = (2x + 3) mod 11. This is a bijection on {0, 1, ..., 10} because modular linear functions with a coefficient coprime to the modulus are bijections. The graph is a single cycle of length 11. Floyd's would detect this instantly, and the “cycle entry” would just be wherever you started walking. There is no tail to traverse.

Case 2: The function has collisions (non-injective). If two different inputs, say a and b, both map to the same output c, then node c has two incoming edges. This convergence is what creates the rho shape. Nodes that feed into c but are not part of the cycle form a tail. The cycle itself exists because the function, being finite, must eventually revisit a state. But the tail exists because collisions mean some nodes are “consumed” by the convergence -- they point into the cycle but are not themselves part of it.

Consider f(x) = (x^2 + 1) mod 7. Both x = 1 and x = 6 produce f(x) = 2. Both x = 2 and x = 5 produce f(x) = 5. These collisions create convergence points, and the resulting graph has tails feeding into cycles. This is the classic rho shape that Floyd's is designed to detect.

Case 3: The function has fixed points. A fixed point is a value where f(x) = x -- the function maps it to itself. In the graph, this is a self-loop: a cycle of length 1. It is the shortest possible cycle. Floyd's detects it trivially: on the very first step, the slow pointer stays at x, the fast pointer goes to f(f(x)) = f(x) = x, and they immediately collide. f(x) = x^2 mod 10 has fixed points at 0, 1, 5, and 6 (since 0^2 = 0, 1^2 = 1, 5^2 = 25 ≡ 5 mod 10, 6^2 = 36 ≡ 6 mod 10).

The key insight is structural: bijections create pure cycles, collisions create rho shapes, and fixed points create length-1 cycles. The “shape vocabulary” of finite functions is surprisingly small, and Floyd's handles all of them.

Study the three functions below. Their complete graphs are shown -- your job is to analyze the structure, not trace the chain.

Floyd's cycle detection works identically across all three domains you have explored: arrays with duplicates, digit-square sequences, and arbitrary functions over finite sets. The code is the same. The pointer movements are the same. The collision logic is the same. But the meaning of what Floyd's tells you -- and which parts of the algorithm you actually need -- changes dramatically depending on the domain.

In the duplicate-number problem, you need both phases of Floyd's. Phase 1 detects the cycle by running slow and fast pointers until they collide somewhere inside the loop. But the collision point is not the answer -- it is just proof that a cycle exists, plus a landmark inside that cycle. The actual answer is the cycle entry -- the specific index where the tail meets the cycle. This is where two different array positions point to the same index, which means two positions hold the same value. To find the entry, you need Phase 2: reset one pointer to the start, walk both pointers one step at a time, and the mathematical relationship between tail length and collision position guarantees they converge at the entry. Skipping Phase 2 is the most common mistake in interviews. You would know a cycle exists but be unable to name the duplicate.

In the happy number problem, you only need Phase 1. The question is binary: does the sequence reach the fixed point 1, or does it cycle through non-1 values? You never need to identify which value the cycle starts at. You never need the cycle entry. Detection alone answers the question. If slow and fast meet at 1, the number is happy -- the sequence terminated at a fixed point. If they meet at anything other than 1, the number is unhappy -- the sequence is trapped in a loop that does not include 1. Phase 2 is unnecessary because the problem does not ask “where does the cycle start?” -- it asks “does the sequence terminate?” This simplification means the happy-number solution is shorter and faster than the duplicate-finding solution, even though both use the same algorithm.

In a permutation (a bijection), the graph structure is fundamentally different from the other two domains. There is no tail. Every element is part of a cycle. The “cycle entry” is wherever you started walking -- since there is no tail, there is no distinction between “entering” the cycle and “already being in it.” Floyd's Phase 1 still works (slow and fast will collide somewhere in the cycle), but Phase 2 is degenerate -- both pointers are already at the entry because the entry is the starting point. The entire graph is one big ring. In permutations, Floyd's is still useful -- you can measure the cycle length by counting steps after collision -- but it answers a different question than in the other two domains.

These structural differences are not academic trivia. They determine how you use Floyd's in practice. In a coding interview, recognizing whether you need Phase 1 only (happy numbers) or both phases (duplicate detection) is the difference between a complete solution and an incomplete one. Understanding that permutations have no tail tells you that the rho-finding logic is unnecessary -- the entire structure is cyclic. The algorithm is a general-purpose tool; the domain dictates which parts of the tool you reach for and what the output means.

Match each structural property to the domain where it applies.

You have now seen Floyd's algorithm applied to linked lists (in earlier modules of this track) and to arrays (in this module). The natural question is: how different are the two implementations, really? The answer is startling. They are almost identical. The entire “conceptual leap” of this module -- arrays are linked lists in disguise, duplicates are cycles, Floyd's applies to both -- collapses into a single mechanical substitution in the code.

Let us lay both versions side by side, line by line.

Initialization. In a linked list, you start both pointers at the head node: slow = head, fast = head. In the array, the “head” is index 0 (because no value in the range [1, n] can point to index 0, making it the unique entry point). So: slow = 0, fast = 0. The structure is identical -- only the name of the starting position changes.

Phase 1 advancement. In a linked list, the slow pointer follows one link: slow = slow.next. The fast pointer follows two: fast = fast.next.next. In the array, .next does not exist. But arr[slow] does. The value at index slow is the “next” index in the chain. So slow = slow.next becomes slow = arr[slow]. And fast = fast.next.next -- which means “follow .next twice” -- becomes fast = arr[arr[fast]]: look up the value at fast to get an intermediate index, then look up the value at that index. The nesting replaces the chaining.

Collision check. In both versions, you check slow == fast. In the linked list, you are comparing node references. In the array, you are comparing index values. The check is textually identical.

Phase 2 advancement. After collision, one pointer resets to the start and both advance at the same speed. In the linked list: slow = head, then slow = slow.next and fast = fast.next in a loop. In the array: slow = 0, then slow = arr[slow] and fast = arr[fast] in a loop. Same structure.

Result. When the two pointers meet in Phase 2, the linked-list version returns the node (the cycle entry). The array version returns the index where they meet -- and arr[that_index] is the duplicate value. Actually, since the meeting point is the index that multiple arrows point to, the duplicate is the value of arr at any of the source indices. But more directly: the meeting index is the duplicate value, because the cycle entry is the index k such that two different positions have arr[i] = arr[j] = k.

The reason the translation is so clean is that the abstraction is genuine. The array, interpreted through f(i) = arr[i], is a linked list. Each index is a node. Each value is a .next pointer. The “head” is index 0. The cycle exists because pigeonhole forces a collision. The only thing that changes between the two implementations is the interface for traversal: .next becomes arr[i]. Everything else -- the algorithm, the phases, the mathematical guarantee about convergence -- is exactly the same.

Below are the two implementations side by side. Connect each line in the linked-list version to its array equivalent.

You have traced rho shapes in arrays, computed them from digit sequences, analyzed them in arbitrary functions, and mapped the code between linked lists and arrays. Every one of those was a rho that someone else designed. Now it is your turn.

The deep principle behind everything in this module is that Floyd's cycle detection works on any function f: S → S where S is finite. Not just linked lists. Not just arrays. Not just digit-square sums. Any function on a finite domain. The pigeonhole principle guarantees that iterating such a function must eventually revisit a state -- creating either a fixed point or a cycle. The shape of the resulting graph depends entirely on the function's behavior: how many collisions it has (which determines the tail lengths), how many distinct cycles it contains, and how large those cycles are. But the existence of a revisit -- and Floyd's ability to detect it -- is guaranteed by finiteness alone.

This is the abstraction that transfers across every problem you will encounter. You do not need a linked list. You do not need an array with a specific constraint. You do not need digits or squares. You need exactly two things: a function and a finite domain. Anywhere those two ingredients exist, Floyd's applies. The two-pointer technique you learned for linked lists is not a linked-list algorithm. It is a function iteration algorithm. Linked lists just happen to be the first context where most programmers encounter it.

To drive this home, let us visit one more domain: pseudo-random number generators. A PRNG is a function that takes a “seed” (a current state) and produces the next state. The function is deterministic -- the same seed always produces the same next state. And the state space is finite (limited by the register width or the modulus). So a PRNG is exactly f: S → S with finite S. If you iterate a PRNG long enough, it must cycle. The length of the cycle is the PRNG's period, and it is one of the most important quality metrics for a random number generator. A short period means the generator repeats quickly and produces statistically poor output. A long period is necessary (though not sufficient) for simulation, cryptography, and Monte Carlo methods. Floyd's algorithm can measure the period in O(1) space -- no need to store the entire history of states.

This PRNG application is not theoretical. Pollard's rho algorithm for integer factorization uses Floyd's cycle detection on the function f(x) = (x^2 + c) mod n to find factors of large numbers. The “rho” in Pollard's rho is the same rho shape you built from an array three screens ago. The same structure, the same detection algorithm, applied to number theory.

Below are two warm-up questions that test your understanding in this novel PRNG domain, followed by a construction challenge. You will design a function f: {0..4} → {0..4} that produces a rho with exactly the tail length and cycle length specified. This is not pattern matching. You must reason about the structure from scratch: which nodes should form the tail, which should form the cycle, and how the edges between them must be arranged to produce the exact shape. If your function has the wrong tail length or cycle length, you will see diagnostic feedback telling you what went wrong. Adjust your function and try again until the shape matches.