Find the Duplicate Number Easy 0 attempts
LeetCode ↗

Find the Duplicate Number

Easy ArrayTwo Pointers LeetCode

Given an array nums containing n + 1 integers where each integer is in the range [1, n] inclusive, there is exactly one repeated number. Find and return it. You must not modify the array and must use only O(1) extra space.

Example 1:

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

Example 2:

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

Edge cases: The duplicate may appear more than twice. The array always has at least two elements.

Sample Input
nums = [1,3,4,2,2]
Sample Output
2
Constraints
  • 1 <= n <= 10^5
  • nums.length == n + 1
  • 1 <= nums[i] <= n
Test Cases
Case 1
Args: [[1,3,4,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.

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