Find the Duplicate Number — Floyd's Cycle Detection on an Array

Problem Statement#

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive, there is only one repeated number in nums. Return this repeated number. You must solve the problem without modifying the array nums and using only constant extra space.

Constraints:

• 1 <= n <= 10^5
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times

Example 1:

Input:  nums = [1, 3, 4, 2, 2]
Output: 2

Example 2:

Input:  nums = [3, 1, 3, 4, 2]
Output: 3

Example 3:

Input:  nums = [3, 3, 3, 3, 3]
Output: 3

Why This Problem Matters#

Find the Duplicate Number (LeetCode 287) is one of the most elegant problems in all of LeetCode. Amazon, Google, and Facebook ask it because the optimal solution requires seeing a non-obvious structural equivalence: this array problem is secretly a linked list problem. Once you see that the array defines an implicit linked list via index → value mappings, Floyd's cycle detection (LC 141/142) solves it directly.

The problem is carefully designed to rule out simpler approaches. You cannot sort the array (that would take O(n log n) and is considered "modifying" by some standards). You cannot use a hash set (O(n) space). You cannot use binary search on the count of elements below mid (O(n log n) time). The optimal solution is O(n) time and O(1) space — exactly Floyd's algorithm.

This problem demonstrates a meta-skill that great engineers possess: recognizing when a problem in one domain (arrays) is isomorphic to a problem in another domain (linked lists) where you have a powerful tool. The ability to see these structural equivalences across different data representations is what separates strong candidates from excellent ones.

Beyond interviews, this insight applies to compiler design (detecting cycles in type dependency graphs encoded as arrays), graph algorithms (detecting cycles in adjacency-represented graphs), and certain computational biology applications.

The Core Insight#

The key observation: Treat each index i as a node and each value nums[i] as a pointer to the next node. This defines an implicit linked list:

• Node 0 → nums[0]
• Node 1 → nums[1]
• ...
• Node i → nums[i]

Since nums has n+1 elements with values in [1, n], and there's a duplicate, two different indices point to the same value. That means two "nodes" have the same "next" pointer — creating a cycle, exactly like a linked list where two nodes' .next pointers point to the same node.

The duplicate value is the cycle entry point. Floyd's Cycle II (LC 142) finds the cycle entry point in O(n) time and O(1) space.

Starting point: Both slow and fast start at nums[0] (not index 0, but the value nums[0]). We start at value nums[0] because index 0 can never be pointed to by any value (values are in [1, n], not 0).

Visual Dry Run#

Input: nums = [1, 3, 4, 2, 2]

The implicit linked list:

• Start at nums[0] = 1 → nums[1] = 3 → nums[3] = 2 → nums[2] = 4 → nums[4] = 2 → nums[2] = 4 → ... (cycle!)

The cycle: 2 → 4 → 2 → 4 → ... (cycle length 2), cycle entry = 2

Phase 1: Detect meeting point

slow = 2, fast = 2 — meeting at value 2.

Phase 2: Find cycle entry (= duplicate)

Reset slow to nums[0] = 1. Keep fast at 2. Move both 1 step at a time.

slow = 2, fast = 2 — both at 2. Cycle entry = 2 = duplicate.

Solution (Optimal)#

Python#

def findDuplicate(nums):
    # Phase 1: Detect meeting point in the implicit linked list
    slow = nums[0]
    fast = nums[0]
 
    while True:
        slow = nums[slow]           # one step: follow one pointer
        fast = nums[nums[fast]]     # two steps: follow two pointers
        if slow == fast:
            break
 
    # Phase 2: Find cycle entry (= the duplicate number)
    slow = nums[0]   # reset one pointer to the start
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
 
    return slow  # both pointers meet at the duplicate

Time complexity: O(n) — Floyd's algorithm on the implicit linked list.

Space complexity: O(1) — only two integer variables (no array allocation).

JavaScript#

var findDuplicate = function(nums) {
    // Phase 1: Detect
    let slow = nums[0];
    let fast = nums[0];
 
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow !== fast);
 
    // Phase 2: Find entry
    slow = nums[0];
    while (slow !== fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
 
    return slow;
};

Complexity:

Simpler alternatives (for comparison):

# Hash set — O(n) space
def findDuplicate(nums):
    seen = set()
    for n in nums:
        if n in seen:
            return n
        seen.add(n)
 
# Sort — O(n log n) time, modifies array
def findDuplicate(nums):
    nums.sort()
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]:
            return nums[i]
 
# Binary search on count — O(n log n) time, O(1) space
def findDuplicate(nums):
    lo, hi = 1, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        count = sum(1 for n in nums if n <= mid)
        if count > mid:
            hi = mid
        else:
            lo = mid + 1
    return lo

Common Mistakes#

1. Starting at index 0 instead of value nums[0]. In LC 142, slow = fast = head (the node). Here, slow = fast = nums[0] — the starting value, not the index. Starting at index 0 directly would make index 0 part of the traversal path, but 0 can never appear as a value (values are in [1, n]), so it would be a dead end.

2. Using do-while vs while in Phase 1. Both slow and fast start at nums[0]. If you use a regular while slow != fast before the first iteration, they're equal (both = nums[0]) and the loop exits immediately — you'd skip Phase 1 entirely. Use do-while or advance once before checking, as in the Python while True: ... if slow == fast: break.

3. Resetting fast instead of slow in Phase 2. In Phase 2, reset one pointer to nums[0] (the start). It doesn't matter which you reset, but don't reset both — you need one at the meeting point.

4. Trying to use this when the array can have 0 as a value. If 0 can appear as a value, index 0 becomes reachable and the cycle structure changes. The constraint 1 <= nums[i] <= n is essential. Verify this constraint before applying Floyd's.

5. Confusing "duplicate number" with "duplicate index". You're finding the value that appears more than once, not the index. The answer is the value (which equals the cycle entry point).

Interview Tips#

1. State the insight explicitly: "The key observation: treat each index as a node and each value as a pointer. Since values are in [1, n] and there's a duplicate, two indices point to the same value — creating a cycle. Floyd's algorithm finds the cycle entry, which is the duplicate."

2. Draw the implicit linked list: For [1, 3, 4, 2, 2], draw: 0→1→3→2→4→2 (cycle at 2). This visualization makes the solution obvious.

3. Explain why we start at nums[0]: "Values are in [1, n], so index 0 is never a destination. We start at nums[0] — the entry into the linked list."

4. Explain the do-while: "Slow and fast start equal (nums[0]). A regular while slow != fast would exit immediately. I use do-while or break-after-check to ensure at least one step."

5. Mention the constraints that enable this: "This works because: (1) values are in [1, n], (2) exactly one duplicate exists, (3) we can't modify the array and need O(1) space. These constraints together make Floyd's the right tool."

Follow-up Questions#

Q: What if the array can have zeros? If 0 can appear as a value, index 0 is reachable and the "start at nums[0]" convention breaks. You'd need to ensure index 0 is a valid starting node. The constraint 1 <= nums[i] <= n is what makes Floyd's work here.

Q: What if there are multiple duplicates? The problem guarantees exactly one duplicate. If there were multiple, Floyd's would still find one cycle entry (one duplicate) but not necessarily all duplicates.

Q: Can you solve it with binary search in O(n log n)? Yes — binary search on the answer space [1, n]. For each mid, count how many elements are <= mid. If count > mid, the duplicate is in [1, mid]. This is O(n log n) time, O(1) space — worse time than Floyd's but no cycle insight needed.

Q: Why can't you just sort the array? The problem says "do not modify the array." Sorting is O(n log n) and modifies in place. You could copy the array and sort the copy, but that's O(n) space.

Q: Is there a bitwise XOR solution? XOR works for finding a single missing element (where each number appears exactly once except one). For finding a duplicate (one appears twice, others appear once), XOR would cancel them out — it doesn't work directly. Floyd's is the canonical O(1) space, O(n) time solution.

Key Takeaways#

• Treat the array as an implicit linked list: index i is a node, nums[i] is its next pointer. The duplicate creates a cycle.
• Floyd's Phase 1: start slow and fast at nums[0], advance at 1x and 2x speed until they meet. Use do-while to avoid premature exit.
• Floyd's Phase 2: reset one pointer to nums[0], move both at 1x until they meet — the meeting point is the duplicate.
• Values must be in [1, n] for this to work — index 0 must be unreachable as a destination.
• O(n) time, O(1) space — the constraints (no modification, constant space) make Floyd's the only optimal solution.
• This is the canonical example of recognizing an array problem as an implicit linked list problem — a meta-skill for advanced interviews.