A warehouse ingest file is supposed to list bin ids in 1..n, plus one extra row. Exactly one id is reused — it may show up more than twice. The intern sorted the file. Compliance said do not rewrite scan order. The intern hashed ids into a set. The memory budget was two integers. Nested comparison on a million-row ingest was still running when the dock cutoff passed.

Find the Duplicate asks for the cycle entrance if nums[i] is next. An array of length n + 1 with values in 1..n is already a next-pointer table. Sorting finds adjacent equals and permutes the file. A set finds the first collision and spends O(n) extra. Both usually violate the prompt.

This is an interview writeup, not a graph-coloring lecture. Floyd’s name is enough for the two speeds. Here we only care that two indexes share a next hop, so the walk from 0 enters a loop at the duplicated value.

The problem

Given an int[] nums of length n + 1 whose values all lie in 1..n, exactly one value is duplicated. That value may appear twice or more; every other value in the range appears at most once. Return the duplicate. Do not modify nums. Extra memory should stay O(1).

nums = [2, 5, 1, 3, 5, 4]   length 6, range 1..5   →  5
nums = [1, 1]               length 2, range 1..1   →  1
nums = [2, 2, 2]            length 3, range 1..2   →  2

Note: [2, 2, 2] is legal: 2 is the only repeated id, and 1 never appears. A frequency map still works. XOR of the file against 1..n does not — the missing ids and the extra copies no longer cancel to one value.

Sort or a set is the honest brute force

Sort, then return the first adjacent pair that matches. Correct, O(n log n), and it rewrites the array. A HashSet that returns on the first failed add is the same answer in expected linear time with O(n) extra — Contains Duplicate with the colliding value instead of a boolean.

int findDuplicateSet(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int x : nums) {
        if (!seen.add(x)) {
            return x;
        }
    }
    throw new IllegalStateException("no duplicate");
}

Both break the usual constraints. Nested comparison of every pair keeps O(1) extra and still pays O(n²). At a million rows you paid a tally for a question the next-hop table already asks: which index has two incoming hops?

Floyd: meet on the loop, then walk to the entrance

Treat index i as a node whose only edge goes to nums[i]. Values are 1..n and indexes are 0..n, so every hop is in range. Nothing stores 0, so index 0 has indegree zero — it is the start of the walk, not a value in the file.

Because one value d appears at least twice, at least two nodes point at index d. That shared hop is a cycle, and d is the entrance. Floyd finds it with two speeds, then a reset — the same meet-then-entrance split you would run on a list, without allocating nodes.

Both walkers start at 0. Move before you compare (they are equal at the start). slow takes one hop; fast takes two. When they meet, they are on the loop. Put slow back at 0 and step both one hop at a time. The next meeting is the entrance — the duplicate.

nums = [2, 5, 1, 3, 5, 4]
hops:  0 → 2 → 1 → 5 → 4 → 5 → …

phase 1 (meet)
  start     slow=0  fast=0
  step      slow=2  fast=1
  step      slow=1  fast=4
  step      slow=5  fast=4
  step      slow=4  fast=4     meet

phase 2 (entrance)
  reset     slow=0  fast=4
  step      slow=2  fast=5
  step      slow=1  fast=4
  step      slow=5  fast=5     entrance 5

The Java is those two walks:

int findDuplicate(int[] nums) {
    int slow = 0;
    int fast = 0;
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    slow = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

Time is O(n) — each phase walks a linear number of hops. Space is O(1) besides the two indexes. You never sort. You never allocate a set. You never write nums[i].

Note: Reset to index 0, not nums[0]. The start of the functional graph is index 0. After the first phase the meeting node is on the cycle, not necessarily the entrance; phase two is not optional.

What interviewers usually poke next

  • Binary search on counts. For a mid in 1..n, count how many values are <= mid. If that count is greater than mid, the duplicate sits in the lower half. O(n log n) time, O(1) extra, no mutation, no Floyd. Name it when they balk at the cycle reading.
  • Mutation allowed. Sort and compare neighbors, or negate the index you visit and watch for a second hit. Say you are rewriting the file they usually forbade.
  • XOR against 1..n. Works only when the extra appears exactly twice and every other value appears once. [2, 2, 2] breaks it. Do not offer it as the general answer.
  • Return every duplicate. This prompt guarantees one repeated value. Several distinct repeats is a different job; a set or a sort then becomes honest again.
  • Why not a coloring DFS. Out-degree is one. Two indexes and Floyd are the procedure; an adjacency walk and colors are the general-graph bill.

You are done with this problem when you can say, out loud, why a set and a sort find the answer and still break the prompt, why nums[i] is a next pointer, and why the second walk after the meeting is the duplicate — not the meeting itself.