Find the Duplicate Number

MediumCyclic SortNeetCode 150MidOpen on LeetCodeUpdated Sep 21, 2026

You're given an array nums of n + 1 integers, each between 1 and n inclusive. With more slots than possible values, some value must repeat; exactly one value repeats, though it may appear two or more times. Return that value. You must not modify nums, and you may use only O(1) extra space.

Examples

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

n = 4 and the five values fall in 1 to 4. 2 appears at indices 3 and 4; every other value appears once.

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

3 appears at indices 0 and 2. The other values, 1, 2 and 4, each appear once.

nums = [3,3,3,3,3] returns 3

The repeated value can appear more than twice, and other values from 1 to 4 can be missing entirely. Here 3 fills every slot.

Constraints

1 <= n <= 10^5
nums.length == n + 1, nums[i] in [1, n]

Hints

Hint 1

If you view the array values as pointers to next indices, what does the duplicate become?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Treat each index i as a node with an edge to index nums[i]. No value is 0, so nothing leads back to index 0, and a walk from there must fall into a loop. The loop's entry has two incoming edges, meaning two indices share its value: that's the duplicate. Floyd's algorithm finds it: step slow once and fast twice until they meet, restart slow at the start, then step both once until they meet at the entry.

Time

O(n)

Space

O(1)

Pitfall

Restart the second phase from the same node the first phase began at (nums[0] in this code). Restarting from index 0 instead shifts the walk by one step and returns 4 for [1,3,4,2,2].

Solutions

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0], fast = nums[0];
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

class Solution:
    def findDuplicate(self, nums):
        slow = fast = 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