Arrays & Hashing · 168Medium
Find All Duplicates in an Array
Given an integer array nums of length n where every value is in [1, n] and each value appears ONCE or TWICE, return an array of all the values that appear twice. Any order is accepted.
Constraints
- n == nums.length, 1 <= n <= 10^5
- 1 <= nums[i] <= n
- Each element appears once or twice.
- You must write an algorithm that runs in O(n) time and uses only constant extra space.
Examples
findDuplicates([4, 3, 2, 7, 8, 2, 3, 1]) -> [2, 3] // any order findDuplicates([1, 1, 2]) -> [1] findDuplicates([1]) -> [] // n = 1, no duplicate possible findDuplicates([1, 1]) -> [1] // smallest duplicate case findDuplicates([1, 2, 3, 4]) -> [] // a permutation of 1..n findDuplicates([2, 1, 2, 1]) -> [2, 1] // every value duplicated; any order
Edge cases
- No duplicates at all returns [].
- Every value duplicated (n is even, n/2 answers).
Show the target complexity (spoiler)
- Naive
- O(n) time, O(n) space — a Set of seen values.
- Target
- O(n) time, O(1) extra space — for each |v|, if nums[|v| - 1] is already negative, v is a duplicate; otherwise negate it.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/01-arrays-hashing/168-find-all-duplicates-in-an-array.js ./practice c 168