Find the Duplicate Number

Share

Given an array of n+1 integers where each integer is between 1 and n, find the duplicate number. Must not modify the array and use only O(1) extra space.

Example 1
Input: [1,3,4,2,2] → Output: 2
Example 2
Input: [3,1,3,4,2] → Output: 3

Solution Approach

Treat array as a linked list with cycle (Floyd's algorithm). Index i points to nums[i]. The duplicate creates a cycle. Find the cycle start.

  • Use slow = nums[nums[slow]] and fast = nums[fast] (like linked list).
  • Find intersection point inside cycle.
  • Then use two slow pointers from start and intersection to find cycle entrance (= duplicate).
Java
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;
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(1)