find duplicate in an array of N+1 Integers

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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);
}
}