find duplicate in an array of N+1 Integers
Problem
An array has n + 1 integers, each in the range 1..n, so at least one value repeats. Exactly one value is repeated (possibly several times). Return it without modifying the array, using O(1) extra space.
Example 1
Input: [1, 3, 4, 2, 2] Output: 2
Example 2
Input: [3, 1, 3, 4, 2] Output: 3
Also asked as: find the duplicate number
Test cases
Case 1
Input: [1,3,4,2,2] Expected: 2
Case 2
Input: [3,1,3,4,2] Expected: 3
Case 3
Input: [3,3,3,3,3] Expected: 3
View solutionHide solution3 approaches
1. Floyd's cycle detection
Time O(n)Space O(1)
Treat values as next-pointers. A duplicate creates a cycle; the entry to the cycle is the duplicate. No mutation, O(1) space.
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;}2. Marking with sign / index
Time O(n)Space O(1)
Walk the array; negate nums[|x|]. If already negative, |x| is the duplicate. Mutates the input.
function findDuplicate(nums) { for (const n of nums) { const i = Math.abs(n); if (nums[i] < 0) return i; nums[i] = -nums[i]; }}3. Hash set
Time O(n)Space O(n)
First value already in the set is the answer. Simplest; O(n) extra space.
function findDuplicate(nums) { const seen = new Set(); for (const n of nums) { if (seen.has(n)) return n; seen.add(n); }}