MEDIUM

Find the Duplicate Number

Given an array nums of n + 1 integers where every value lies in the range [1, n], exactly one value repeats (possibly more than twice). Find that duplicate without modifying the array and using only O(1) extra space.

Example

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

Output 2

Key Pointers

Treat the array as an implicit linked list where index i "points to" index nums[i] — a duplicate value creates a cycle in that list.
That reframing turns the problem into the exact same Floyd's cycle detection used for Linked List Cycle, just walking array indices instead of node pointers.
Finding the meeting point alone isn't enough — a second phase pinpoints the actual cycle entrance, which is the duplicate value.

Step-by-Step Analysis

Initialize slow = nums[0], fast = nums[0].
Phase 1: move slow = nums[slow] and fast = nums[nums[fast]] until slow == fast.
Phase 2: reset slow = nums[0]; advance both slow and fast one step at a time until they meet again.
That second meeting point is the duplicate — return it.

Complexity

Time: O(n) — Space: O(1)

Code

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

    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

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

    return slow

Code Explanation

How the solution above works, piece by piece.

Values are in 1..n and there are n + 1 of them, so following i → nums[i] from index 0 never leaves the array and must eventually loop.
The duplicate value is the node two different indices point to, which is exactly where the path enters the loop.
Phase 1 (like Linked List Cycle): slow takes one hop, fast two, until they meet somewhere in the loop.
Phase 2: restart slow at the beginning and move both one hop at a time. The distance maths of Floyd's algorithm makes them meet exactly at the loop entry.
O(n) time and O(1) space, without modifying the array.

Visual Walkthrough

Running it on nums = [1, 3, 4, 2, 2]:

Treat each index as a node with an arrow to nums[i]. Two indices (3 and 4) both point to 2, so 2 is where the path enters a loop, and that entry node is the duplicate. Floyd's algorithm finds a meeting point in the loop, then the loop's entry.

duplicate / loop entrythe loop

Video Explanation

NeetCode — Floyd's Cycle Detection, LeetCode 287