Find All Duplicates in an Array

Medium

Problem

An array of n integers has every value in 1..n, and each value appears once or twice. Return every value that appears twice, in O(n) time and O(1) extra space.

Example 1

Input:  [4, 3, 2, 7, 8, 2, 3, 1]
Output: [2, 3]

Test cases

Case 1

Input:    [4,3,2,7,8,2,3,1]
Expected (any order): [2,3]

Case 2

Input:    [1,1,2]
Expected (any order): [1]

Case 3

Input:    [1]
Expected (any order): []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Mark by negating

Time O(n)Space O(1) extra

Visiting v flips nums[v − 1] negative; if it is already negative, v has been seen before.

function findDuplicates(nums) {
const res = [];
for (const x of nums) {
const i = Math.abs(x) - 1;
if (nums[i] < 0) res.push(i + 1);
else nums[i] = -nums[i];
}
return res;
}