Find the Duplicate Number

1. Problem & Core Objective

An array nums of n + 1 integers, each in the range [1, n]. Exactly one value is repeated — possibly many times. Return it.

You must not modify the array, and you must use only O(1) extra space.

nums = [1,3,4,2,2]      → 2
nums = [3,1,3,4,2]      → 3

Constraints: 1 <= n <= 10^5 · all values in [1, n] · exactly one value repeats

What's actually being tested: whether you can see an array as a linked list. The two constraints — don't modify, O(1) space — exist specifically to rule out sorting and hashing, leaving cycle detection as the only way through. It's the least obvious application of Floyd's in the 150.

2. First-Principles Thought Process

The constraints are the question

Read what's forbidden:

• Can't modify → no sorting, no marking elements by negating them.
• O(1) space → no HashSet, no count array.

Both natural solutions are explicitly blocked. When constraints eliminate every obvious approach, they're pointing at a specific technique.

Reading the array as a function

The values are in [1, n] and the indices are in [0, n]. So i → nums[i] is a map from indices to valid indices. That means you can iterate it:

0 → nums[0] → nums[nums[0]] → ...

This is a walk. Every step lands somewhere legal — the walk can never run off the end.

Why a cycle must exist

There are n + 1 slots and the walk never terminates, so by pigeonhole it must revisit a node. An infinite walk in a finite space is a cycle. This is guaranteed, not lucky.

Why the cycle entrance is the duplicate

A node has two arrows pointing into it exactly when two different indices hold the same value — that is, when the value is duplicated. The cycle entrance is the first node reachable by two different paths, so the entrance is the repeated value.

Starting at index 0 is safe because values are in [1, n], so nothing ever points back to index 0 — index 0 is outside the cycle, giving the walk a proper tail. That's what makes the a = c argument from question 7 apply.

So the problem becomes

Find the entrance of the cycle in this implicit list — which is exactly LeetCode 142, solved with Floyd's in O(1) space.

3. Solution Paths

Approach 1 — Sort, then scan for adjacent equals (brute force)

public int findDuplicate(int[] nums) {
    int[] copy = nums.clone();          // the problem forbids modifying nums
    Arrays.sort(copy);
    for (int i = 1; i < copy.length; i++)
        if (copy[i] == copy[i - 1]) return copy[i];
    return -1;
}

• Time O(n log n) · Space O(n) for the copy

Counter-questions on this approach

⭐ "You cloned to avoid mutating. Did that fix the violation?"

No — it traded one violation for another. The problem forbids modifying the array and forbids O(n) extra space, and the clone is O(n). Sorting in place would honour the space limit but break the no-modify rule. Either way one of the two constraints is broken, which is the signal that sorting simply isn't the intended tool.

"What if you were allowed to modify it?"

Then in-place sorting gives O(n log n) time and O(1) space and is a legitimate answer. Or better: since values are in [1, n], you could mark by negating nums[|v|] and report the first index already negative — O(n) time, O(1) space. Both are blocked here, but worth naming, because they show the constraints are doing deliberate work rather than being arbitrary.

"Is O(n log n) fast enough at n = 10^5?"

Comfortably — about 1.7 × 10^6 operations. Speed isn't the objection; the constraint violation is.

Approach 2 — Hash set (brute force, also blocked)

public int findDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int v : nums) if (!seen.add(v)) return v;
    return -1;
}

• Time O(n) · Space O(n)

Counter-questions on this approach

⭐ "O(n) time is optimal. Why isn't this the answer?"

The space. It's O(n), and the problem explicitly caps extra space at O(1). I'd still write this one first in an interview — it's the obvious solution and it's correct — but I'd say immediately that it violates the stated constraint and that the constraint is what points to the real technique.

"Could you use a bitset to shrink the space?"

It cuts the constant enormously — 10^5 bits is about 12 KB versus a HashSet<Integer> of boxed objects at several megabytes. But O(n/64) is still O(n). It's a genuinely better engineering answer and still not the answer to this question.

"Any O(1)-space approach that isn't Floyd's?"

Yes — binary search on the value range. For a candidate m, count how many elements are ≤ m. If that count exceeds m, the duplicate lies in [1, m], by pigeonhole. That's O(n log n) time and O(1) space, and it doesn't modify the array. It's a legitimate answer and a nice link back to Section 5 — searching the answer space. Floyd's is strictly better at O(n), but this one is much easier to derive under pressure.

Approach 3 — Floyd's cycle detection on the implicit list (optimal)

public int findDuplicate(int[] nums) {
    // phase 1 — find a meeting point inside the cycle
    int slow = nums[0], fast = nums[nums[0]];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }

    // phase 2 — walk from the start and from the meeting point at equal speed
    slow = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;                  // the cycle entrance = the duplicated value
}

Trace — nums = [1,3,4,2,2]:

The implicit chain from index 0 is 0 → 1 → 3 → 2 → 4 → 2 → 4 → …, so the cycle is 2 → 4 → 2 and the entrance is 2.

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "Why is a cycle guaranteed? What if the walk just ends?"

It can't end. Values are in [1, n] and indices in [0, n], so nums[i] is always a valid index — every step lands somewhere legal, and there is no null to reach. An endless walk over n + 1 slots must revisit one by pigeonhole, and a revisit is a cycle. The value range isn't incidental; it's what makes the walk total.

⭐ "Why is the cycle entrance the duplicate, rather than some other node in the loop?"

The entrance is the unique node with two incoming arrows — one from the tail of the walk and one from inside the loop. An arrow i → nums[i] points at node v exactly when nums[i] == v, so two arrows into v means two indices hold v. That's the definition of the duplicate.

Every other node in the cycle has just one predecessor, so the entrance is the only candidate.

⭐ "Why must you start at index 0?"

Because index 0 is guaranteed to be outside the cycle. Values are in [1, n], so no nums[i] ever equals 0 — nothing points back to index 0. That gives the walk a genuine tail before it enters the loop, which is what makes a non-zero and lets the a = c argument from question 7 apply.

Starting anywhere else risks starting inside the cycle, where phase 2 is no longer meaningful.

"Why does phase 2 reset slow to 0 but not fast?"

From question 7: a = c, where a is head-to-entrance and c is meeting-point-to-entrance. So one pointer must walk a from the start and the other c from where they met. Resetting both would just repeat phase 1. Resetting neither never converges.

"Does this modify nums?"

No — it only reads. That's what makes it legal here, and it's the one thing the marking trick can't claim.

"What if there were several distinct duplicated values?"

Then there can be several cycles, and this returns the entrance of whichever the walk from index 0 happens to reach. The problem guarantees exactly one repeated value, and the algorithm leans on that guarantee. Worth stating as a precondition rather than pretending it generalizes.

Comparison

4. Why the Optimal Wins

Floyd's is the only approach that is simultaneously O(n) time, O(1) space, and non-destructive. Binary search on the value range meets the constraints but pays a log n factor; sorting and hashing each break one of the two rules.

The deeper reason it wins is the reframe. The array looks like a flat collection where duplicate-finding means comparing elements. Reading i → nums[i] as a successor function turns it into a graph walk, and the duplicate stops being "a repeated element" and becomes "the node with two predecessors" — a structural property Floyd's was built to find.

The framing worth keeping:

Any array whose values are valid indices is a linked list in disguise. i → nums[i] is a next pointer, and repeated values are where the arrows converge.

The same reading solves First Missing Positive and Find All Duplicates, and it's the mechanism behind Pollard's rho factorisation.

5. Java Prerequisites

Double indexing — the array equivalent of fast.next.next:

fast = nums[nums[fast]];

Safe only because every value is a valid index. Verify that before writing it.

Starting positions. Phase 1 starts slow = nums[0] and fast = nums[nums[0]] — both already advanced once, so the while (slow != fast) loop isn't trivially true at entry. The alternative is a do-while from slow = fast = 0.

No cloning. nums.clone() is O(n) space and breaks the constraint. Read-only access is the whole point.

Arrays.sort on primitives is a dual-pivot quicksort, O(n log n), in place — worth knowing it's not stable for primitives, unlike the merge sort used for objects. See 04.

6. Interview Communication Guide

Clarifying questions: Exactly one value repeats, but possibly many times (yes — both matter)? Truly cannot modify the array (confirm; it rules out marking)? Is O(1) space hard or preferred (confirm)? Values strictly in [1, n] (yes — this is load-bearing)?

The pitch

"The two constraints are the question. No modification rules out sorting and marking; O(1) space rules out a hash set. Both obvious solutions are explicitly blocked, which tells me a specific technique is wanted.

The way in is the value range. Values are in [1, n] and indices in [0, n], so nums[i] is always a valid index. That means I can read the array as a linked list: i → nums[i] is a next pointer.

Because every step lands on a legal index, the walk never terminates — and an endless walk over n+1 slots must revisit a node. So a cycle is guaranteed, not hoped for.

And the cycle's entrance is the answer. A node has two arrows into it exactly when two indices hold the same value, and the entrance is the only node with two predecessors — one from the tail, one from inside the loop.

I start at index 0 because values are at least 1, so nothing points back to it — index 0 is guaranteed outside the cycle, which gives the walk a proper tail.

Then it's Floyd's, exactly as in the cycle question: phase 1 finds a meeting point, phase 2 resets one pointer to the start and advances both one step at a time until they meet at the entrance.

O(n) time, O(1) space, array untouched.

If I couldn't see that, the fallback is binary search on the value range — count elements ≤ m and use pigeonhole. That's O(n log n) and also meets the constraints."

Edge cases to volunteer:

Name [2,2,2,2,2]. It's a self-loop — the cycle has length 1 — and it's where an implementation that assumes a cycle of length ≥ 2 breaks.

7. Follow-Up Questions — Modified Constraints

⭐ "What if you WERE allowed to modify the array?"

Much easier. Walk the array and for each value v negate nums[|v| - 1]; if it's already negative, |v| is the duplicate. O(n) time, O(1) space, and far more obvious than Floyd's. You can restore the array afterwards by taking absolute values. This is the answer whenever the no-modify constraint is lifted.

⭐ "What if there were k duplicated values rather than one?"

Floyd's breaks — it finds one cycle and can't enumerate the rest. With modification allowed, the negation trick finds them all in O(n) time. Without it, you're back to O(n) space or O(n log n) with repeated binary searches. Worth saying the technique genuinely doesn't extend rather than improvising.

"Explain the binary search alternative properly."

Search the value space [1, n], not the array. For a candidate m, count how many elements are ≤ m in one O(n) pass. If the count exceeds m, then by pigeonhole the duplicate is in [1, m]; otherwise it's above. O(n log n) time, O(1) space, non-destructive. This is exactly the "search the answer space" pattern from Koko Eating Bananas.

"Find the duplicate if values were in [0, n-1] instead."

The walk can now reach index 0 from elsewhere, so index 0 might sit inside the cycle — and then there's no tail, a = 0, and phase 2 is meaningless. You'd need to start from an index known to be outside any cycle, which isn't generally available. Constraints on the value range are doing real work in this problem.

"What is the actual relationship to Pollard's rho?"

The same algorithm. Pollard's rho iterates x → x² + c mod n and uses Floyd's to find where that sequence repeats; a collision reveals a non-trivial factor of n. Identical machinery — a finite domain, an iterated function, and cycle detection — applied to factorisation instead of arrays.

"Could you solve it with bit counting?"

Yes. For each of the ~17 bit positions, count how many numbers in [1, n] have that bit set, and how many in nums do. Where the array's count exceeds the expected count, that bit belongs to the duplicate. O(n log n) time, O(1) space, non-destructive — and it extends to some multi-duplicate variants where Floyd's does not.