{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Find the Duplicate Number – Solution & Complexity

Interview solutions
/
Find the Duplicate Number

Solution Walkthrough

  1. Step 1: Start from the constraints, not from code

    • Sorting would either modify the array or require copying it first.
    • A hash set finds the duplicate quickly, but it uses O(n) extra memory.
    • The intended trick is to treat each index as a node with one outgoing edge: i -> nums[i]. Because values stay in [1, n], following pointers from index 0 must eventually enter a cycle, and the duplicate value is the cycle's entrance.

  2. Step 2: Warm up with a disallowed hash-set solution

    • Scan the array and remember values seen so far.
    • The first value you encounter twice is the answer.
    • This is correct and runs in O(n) time, but it violates the constant-space requirement, so it is only a warm-up.
    def find_duplicate(nums: list[int]) -> int:
    seen = set()
    for num in nums:
        if num in seen:
            return num
        seen.add(num)
    return -1

  3. Step 3: Why Floyd's cycle detection works here

    • Think of index i as a node whose next pointer is nums[i]. Since every nums[i] is between 1 and n, once you move from index 0, you stay inside the node set 1..n.
    • There are n + 1 indices but only n possible next-node values, so following pointers from 0 must eventually revisit a node: a cycle exists.
    • The duplicate value is exactly the first node with two incoming edges on that reachable path, so it is the cycle entrance.
    • Floyd's algorithm first finds any meeting point inside the cycle, then resets one pointer to the start and advances both one step at a time; they meet at the entrance.

  4. Step 4: Apply Floyd's tortoise-and-hare algorithm

    • Start slow one step from the start and fast two steps from the start.
    • Move slow by one edge and fast by two edges until they meet inside the cycle.
    • Then reset a finder pointer to index 0, move finder and slow one step at a time, and return where they meet. That meeting value is the duplicate number.
    def find_duplicate(nums: list[int]) -> int:
    slow = nums[0]
    fast = nums[nums[0]]

    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[fast]]

    finder = 0
    while finder != slow:
        finder = nums[finder]
        slow = nums[slow]

    return finder

  5. Step 5: Dry run on nums = [1,3,4,2,2]

    The pointer graph is 0 -> 1 -> 3 -> 2 -> 4 -> 2 -> ..., so the cycle starts at value 2.

    Phase 1: find a meeting point inside the cycle

    stepslowfast
    start13
    134
    224
    344

    They first meet at value 4, which is inside the cycle but is not necessarily the duplicate.

    Phase 2: find the cycle entrance

    stepfinderslow
    start04
    112
    234
    322

    Now both pointers meet at 2, so the duplicate number is 2.

  6. Step 6: Common mistakes

    • Returning the first slow == fast meeting point directly. That point is somewhere inside the cycle, not always the duplicate value itself.
    • Starting both pointers at nums[0]; that can make them appear to meet immediately before any real progress. Use one step vs. two steps at initialization.
    • Mixing up indices and values, or subtracting 1 as if the graph were zero-based on 1..n. The values already are valid next indices for this construction.
    • Using sorting or a hash set in the final answer, which breaks the read-only or constant-space constraints.

  7. Step 7: Edge cases to test mentally

    • Smallest valid input: [1,1] immediately forms a one-node cycle, so the answer is 1.
    • A duplicate may appear three or more times, such as [2,5,9,6,9,3,8,9,7,1,4]; the entrance is still 9.
    • The duplicate value can appear in the first array slot, the last slot, or only after a long tail before the cycle begins.
    • The answer is the repeated value, not the index of one occurrence.

  8. Step 8: Final full solution and complexity

    Treating the array as a functional graph lets Floyd's cycle detection find the duplicate in O(n) time with O(1) extra space, without modifying nums.

    def find_duplicate(nums: list[int]) -> int:
    slow = nums[0]
    fast = nums[nums[0]]

    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[fast]]

    finder = 0
    while finder != slow:
        finder = nums[finder]
        slow = nums[slow]

    return finder

FAQ

See also

Practice Find the Duplicate Number online (run code in the browser)3Sum solution (medium)3Sum Closest solution (medium)Container With Most Water solution (medium)Linked List Cycle solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?