Find the Duplicate Number: Floyd's on Index-to-Value Mapping

• Problem – given an array of n+1 integers where every value is between 1 and n, exactly one value is duplicated; find it without modifying the array and using O(1) space.
• Key insight – treat each value as a pointer to the next index, forming a functional graph with a guaranteed cycle.
• Floyd's algorithm – a two-phase cycle detection: phase one finds a meeting point inside the cycle, phase two finds the cycle entry.
• Cycle entry – the index where two different positions point to, which is the duplicated value.
• Constraints – read-only array and constant extra space rule out sorting, HashSet, and negation tricks.

What is the Find the Duplicate Number problem?

Given an array of n + 1 integers where every value is in the range [1, n], exactly one value is repeated (possibly more than once). The task is to find the duplicate without modifying the array and using only constant extra space. This rules out sorting (mutates), a HashSet (uses O(n) space), and the negation trick (mutates).

package com.bank.dsa;

public class DuplicateFinder {
    // Find the duplicate in a read-only array
    public int findDuplicate(int[] nums) {
        // implementation below
        return -1;
    }
}

How does the value-as-pointer mapping create a cycle?

Define the successor of position i as nums[i], so moving from index i goes to index nums[i]. Since every value is in [1, n] and there are n + 1 slots, this mapping always stays within bounds. Because one value repeats, two different indices point to the same next index, which forms a cycle. The entry node of that cycle is the duplicated value.

// Example: nums = [1, 3, 4, 2, 2]
// Index:   0  1  2  3  4
// Value:   1  3  4  2  2
//
// Mapping: 0 -> 1 -> 3 -> 2 -> 4 -> 2 -> 4 -> 2 (cycle at 2)
// The duplicate value is 2

How does Floyd's algorithm find the cycle entry?

Phase one starts both pointers at index 0. The slow pointer advances by one step (slow = nums[slow]) and the fast pointer by two steps (fast = nums[nums[fast]]). They are guaranteed to meet inside the cycle.

Phase two resets one pointer to index 0 and advances both by one step until they meet. The meeting point is the cycle entry, which is the duplicate value.

package com.bank.dsa;

public class FloydDuplicateFinder {
    public static int findDuplicate(int[] nums) {
        // Phase 1: find meeting point inside cycle
        int slow = nums[0];
        int fast = nums[nums[0]];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        // Phase 2: find cycle entry
        int finder = 0;
        while (finder != slow) {
            finder = nums[finder];
            slow = nums[slow];
        }
        return finder;
    }

    public static void main(String[] args) {
        int[] branchCodes = {1, 3, 4, 2, 2};
        System.out.println("Duplicate: " + findDuplicate(branchCodes));
    }
}

Duplicate: 2

Why does the cycle entry equal the duplicate?

The reason is the same algebra as Linked List Cycle II. When slow and fast meet, they are at a distance from the cycle entry that equals the distance from the start to the cycle entry, modulo the cycle length. Resetting one pointer to the start and advancing both at equal speed makes them converge exactly at the entry. Here the entry is the value that two indices point into, which is the repeated number.

Start -> ... -> entry -> ... -> meeting point
  |                ^                  |
  |                |  (cycle)         |
  |                +------------------+

Distance: start to entry = meeting to entry (mod cycle length)

Why are other approaches rejected?

Each alternative violates one of the two constraints.

| Approach | Modifies Array? | Extra Space | Notes |
|---|---|---|---|
| Sorting | Yes | O(1) | Mutates input |
| HashSet | No | O(n) | Too much space |
| Negation trick | Yes | O(1) | Mutates input |
| Binary search (value range) | No | O(1) | O(n log n) time |
| Floyd's cycle | No | O(1) | Optimal |

// HashSet approach: O(n) time, O(n) space (violates space constraint)
Set<Integer> seen = new HashSet<>();
for (int num : nums) {
    if (!seen.add(num)) return num;
}

What about starting at index 0 vs a[0]?

Starting slow at nums[0] rather than at index 0 avoids the self-loop at index 0. Since values are in [1, n], index 0 is never pointed to by any value, so it acts as the head of the "linked list" and is guaranteed to be outside the cycle. Starting both pointers from nums[0] enters the chain directly.

// Correct: start from nums[0], not from 0
int slow = nums[0];
int fast = nums[nums[0]];

// Why: index 0 is the head node
// Values are 1..n, so no value points back to 0
// Starting from nums[0] enters the chain

What are edge cases?

Edge cases include the minimum valid input [1, 1] (two elements, duplicate is 1), and an array where the duplicate appears many times such as [2, 2, 2, 2, 2]. Floyd's algorithm handles both correctly because the cycle structure holds regardless of how many times the duplicate appears.

findDuplicate(new int[]{1, 1});           // 1
findDuplicate(new int[]{2, 2, 2, 2, 2}); // 2
findDuplicate(new int[]{3, 1, 3, 4, 2}); // 3

What are common mistakes?

The most common mistake is starting both pointers at index 0 instead of at nums[0], which causes the while loop to not execute because slow == fast immediately. Another is confusing the cycle entry with the meeting point; they are generally different and the second phase is needed to find the entry.

// Wrong: both start at 0, immediately equal
int slow = 0, fast = 0;
while (slow != fast) { ... } // never enters loop

// Correct: start at nums[0] and nums[nums[0]]
int slow = nums[0];
int fast = nums[nums[0]];

What should a senior engineer know?

A senior engineer explains the value-as-pointer reframing, proves the cycle-entry algebra, and states why each alternative is rejected under the given constraints. They note the binary search on value range as a third O(n log n) read-only option for when Floyd's is too tricky to explain under pressure. They also know this is a pigeonhole principle application: n + 1 values in n slots guarantees a repeat.