Find All Duplicates in an Array
Medium · Arrays & Hashing · Array · Hash Table
Problem
You are given an integer array nums of length n. Every value lies in the range [1, n], and each value appears once or twice.
Return all the values that appear twice, in any order.
Aim for O(n) time and O(1) extra space (the output list does not count). Because the values are exactly the valid positions 1..n, the array itself can serve as the "seen" table.
Examples
Input: nums = [5,3,1,3,5,2] Output: [3,5]
3 and 5 each appear twice; 1 and 2 once. The values may be listed in any order.
Input: nums = [2,1] Output: []
Each value appears once.
Input: nums = [1,1] Output: [1]
The only value appears twice.
Constraints
- n == nums.length
- 1 <= n <= 10^5
- 1 <= nums[i] <= n
- Each value appears once or twice
Approaches
- Sort a copy and compare neighbors — time O(n log n), space O(n)
Follow-up
The same sign trick finds the values that never appear (slots still positive at the end) and, with both, the duplicate and the missing value of a corrupted 1..n set. When the input must not change and values can repeat many times, the duplicate-finding problem becomes a cycle search (Floyd) on i -> nums[i].
Related problems
Start free on Cariara · Coding problems · System design studio
