Find All Duplicates in an Array
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): []
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;}