Leetcode - 287. Find the Duplicate Number

Medium

Dec 24, 2025

#linked-list

#array

287. Find the Duplicate Number

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.

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

Constraints:

1 <= n <= 105
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.

How can we prove that at least one duplicate number must exist in nums?
Can you solve the problem in linear runtime complexity?

Follow up:

Notes

Intuition

Treat the array as a linked list where each value points to the next index. Since there's a duplicate, following these "pointers" creates a cycle. The duplicate is where the cycle begins—finding the cycle's start gives us the answer.

Implementation

Use Floyd's cycle detection in two phases. First, use fast and slow pointers until they meet—this confirms a cycle and places slow somewhere inside it. Second, start a new pointer at index 0 and advance both it and slow one step at a time. They'll meet at the cycle's start, which is the duplicate value.

Edge-cases

The first phase only detects that a cycle exists; it doesn't find the start. The second phase is essential for locating the actual duplicate.

Time: O(n) — both phases traverse at most n elements
Space: O(1) — only using pointers

Complexity

Solution

from typing import List

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = 0, 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        slow_2 = 0
        while True:
            slow_2 = nums[slow_2]
            slow = nums[slow]
            if slow == slow_2:
                return slow



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()