Find the Duplicate Number Easy 0 attempts
LeetCode ↗

Find the Duplicate Number

Easy ArrayTwo Pointers LeetCode

You're given an array nums holding n + 1 integers, each falling somewhere between 1 and n inclusive, and exactly one value is repeated in the array. Identify that repeated value, without modifying the array and using only O(1) extra space.

Edge cases: The same value could show up more than twice. The array is guaranteed to contain at least two elements.

Input Format
Implement findDuplicate(nums). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
nums = [1,3,4,2,2]
Output
2

Example 2

Input
nums = [2,2,2,2,2]
Output
2
Constraints
  • 1 <= n <= 10^5
  • nums.length == n + 1
  • 1 <= nums[i] <= n
Test Cases (2)
Case 1
Args: [[1,3,4,2,2]] Expected: 2
Case 2
Args: [[2,2,2,2,2]] Expected: 2
Topics
ArrayTwo Pointers

Approach: Floyd's Cycle Detection

Treat each value as a pointer to the next index. Because there's a duplicate, following these pointers creates a cycle — exactly like a linked list with a loop. Use a slow and fast pointer to detect the cycle, then find the entrance.

javascript
function findDuplicate(nums) {
  let slow = nums[0];
  let fast = nums[nums[0]];

  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[nums[fast]];
  }

  slow = 0;
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }
  return slow;
}

Time Complexity: O(n)

Space Complexity: O(1)

Saved in this browser only. Private to you.

JavaScript