LeetCodee

287. Find the Duplicate Number

Jump to Solution: Python Java C++ JavaScript C#

Problem Description

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 uses 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

Constraints:

  • 1 <= n <= 10⁵
  • 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.

Follow up:

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

Solution

Python Solution

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # Initialize slow and fast pointers
        slow = nums[0]
        fast = nums[0]
        
        # Find intersection point
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        
        # Find entrance to cycle
        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
            
        return slow

Time Complexity: O(n)

Floyd's cycle detection algorithm runs in linear time.

Space Complexity: O(1)

Only uses two pointers regardless of input size.

Java Solution

class Solution {
    public int findDuplicate(int[] nums) {
        // Initialize slow and fast pointers
        int slow = nums[0];
        int fast = nums[0];
        
        // Find intersection point
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        
        // Find entrance to cycle
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        
        return slow;
    }
}

Time Complexity: O(n)

Floyd's cycle detection algorithm runs in linear time.

Space Complexity: O(1)

Only uses two pointers regardless of input size.

C++ Solution

class Solution {
public:
    int findDuplicate(vector& nums) {
        // Initialize slow and fast pointers
        int slow = nums[0];
        int fast = nums[0];
        
        // Find intersection point
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        
        // Find entrance to cycle
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        
        return slow;
    }
};

Time Complexity: O(n)

Floyd's cycle detection algorithm runs in linear time.

Space Complexity: O(1)

Only uses two pointers regardless of input size.

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    // Initialize slow and fast pointers
    let slow = nums[0];
    let fast = nums[0];
    
    // Find intersection point
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow !== fast);
    
    // Find entrance to cycle
    slow = nums[0];
    while (slow !== fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    
    return slow;
};

Time Complexity: O(n)

Floyd's cycle detection algorithm runs in linear time.

Space Complexity: O(1)

Only uses two pointers regardless of input size.

C# Solution

public class Solution {
    public int FindDuplicate(int[] nums) {
        // Initialize slow and fast pointers
        int slow = nums[0];
        int fast = nums[0];
        
        // Find intersection point
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        
        // Find entrance to cycle
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        
        return slow;
    }
}

Time Complexity: O(n)

Floyd's cycle detection algorithm runs in linear time.

Space Complexity: O(1)

Only uses two pointers regardless of input size.

Approach Explanation

The solution uses Floyd's Tortoise and Hare (Cycle Detection) algorithm:

  1. Key Insight:
    • Array can be viewed as a linked list
    • Duplicate creates a cycle in this list
    • Use cycle detection to find duplicate
  2. Algorithm Steps:
    • Find intersection using two pointers
    • Reset slow pointer to start
    • Move both pointers at same speed
    • Meeting point is duplicate

Example walkthrough for [1,3,4,2,2]:

  • Initial: slow = 1, fast = 1
  • First step: slow = 3, fast = 4
  • Second step: slow = 2, fast = 2
  • Reset slow = 1, keep fast = 2
  • Meet at 2 (duplicate number)

Mathematical proof:

  • Pigeonhole principle proves duplicate exists
  • Floyd's algorithm guarantees finding cycle
  • Meeting point must be at cycle entrance
  • Linear time complexity proven

Edge Cases:

  • Duplicate at beginning
  • Duplicate at end
  • Multiple duplicates
  • Minimum array size