Find the Duplicate Number

medium array two pointers cycle detection

Problem

Given an array of n+1 integers where each value is in [1, n], exactly one value is repeated. Find it using O(1) extra space and without modifying the array.

Inputnums = [1, 3, 4, 2, 2]

Output2

The sequence i → nums[i] starting at 0 must contain a cycle because two indices point to the same value — the cycle entrance is the duplicate.

nums (values in [1, n], one repeats)

def findDuplicate(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

function findDuplicate(nums) {
  let 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 {
    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 {
public:
    int findDuplicate(vector<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;
    }
};

Explanation

The clever trick is to treat the array as a linked list: from index i you "follow" the pointer to index nums[i]. Because one value repeats, two different indices point to the same place, which forces a cycle. The duplicate is exactly where that cycle begins.

To find a cycle without extra memory we use Floyd's tortoise and hare. A slow pointer moves one step at a time (slow = nums[slow]) and a fast pointer moves two steps (fast = nums[nums[fast]]). Inside a loop the fast one eventually laps the slow one, so they meet.

That meeting point is somewhere inside the cycle, not necessarily its entrance. So phase two resets slow back to nums[0] and now advances both pointers one step at a time. The spot where they meet again is the cycle's entrance — the duplicate number.

Example: nums = [1, 3, 4, 2, 2]. Following indices from 0: 0 → 1 → 3 → 2 → 4 → 2 → 4 …, which loops between 2 and 4. The cycle entrance is value 2, the duplicate.

This runs in O(n) time using only two integer pointers, so it never modifies the array or uses extra space.

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