Community Problem
Find All Duplicates in an Array
Difficulty: Medium
Identify every value that appears twice in an array of integers in [1, n], using O(1) extra space via index-negation.
Find All Duplicates in an Array
Identify every value that appears twice in an array of integers in [1, n], using O(1) extra space via index-negation.
By @arjunrivera
January 31, 2026
·
Updated May 18, 2026
927 views
29
Rate
I keep this one bookmarked for the moment a candidate finishes a hash-set duplicate detector and tells me "that is the optimal answer." The constraint that values fall in [1, n] and that the array length is n is doing all the work, because it lets you treat the array itself as a hash table by flipping the sign at the index each value points at. The official catalog has Find the Duplicate Number (one duplicate, read-only constraint, Floyd cycle) but skipped the every-duplicate variation that the negation trick handles cleanly.
Find All Duplicates in an Array
Given an integer array nums of length n where every value satisfies 1 <= nums[i] <= n, return an array of all the integers that appear twice in nums. Each integer appears either once or twice. The output may be returned in any order.
Examples
Example 1:
- Input:
nums = [4, 3, 2, 7, 8, 2, 3, 1] - Output:
[2, 3](any order) - Explanation:
2and3appear twice; the rest appear once.
Example 2:
- Input:
nums = [1, 1, 2] - Output:
[1] - Explanation: Only
1appears twice.
Example 3:
- Input:
nums = [1] - Output:
[] - Explanation: A single element cannot be duplicated.
Example 4:
- Input:
nums = [2, 2] - Output:
[2] - Explanation: The single value 2 appears twice.
Constraints
n == nums.length1 <= n <= 10^51 <= nums[i] <= n- Each element appears once or twice.
Follow-up
The natural hash-set solution is O(n) time and O(n) space. Can you do it in O(n) time and O(1) extra space (excluding the output array)? The classic trick uses the input array itself as the bookkeeping structure by negating the value at the index that each nums[i] points to. Treat that as a hint, not a requirement.
Solution
Hints
Solution Walkthrough
Approach: Index-Negation Marking (O(n) time, O(1) extra space)
The idea is to use the array as its own visited-set. Because every value v = nums[i] is in [1, n], the index v - 1 is a legal slot. Walk the array. For each value v = |nums[i]|, look at nums[v - 1]:
- If it is already negative,
vhas been seen before, so it is a duplicate. - Otherwise, negate it to mark
vas visited.
The absolute value is necessary because once a slot has been negated, reading it directly gives a negative number, but the underlying "value" it represents is the magnitude.
Algorithm
- Initialize
result = []. - For each
ifrom0ton - 1:- Let
v = |nums[i]|. - If
nums[v - 1] < 0, pushvtoresult. - Else negate
nums[v - 1]in place.
- Return
result.
Why It Works
Loop invariant after iteration i: for every distinct value v seen in nums[0..i], nums[v - 1] is negative. The first time we see v, the slot at v - 1 is positive, so we negate it (and the invariant gains one entry). The second time we see v, the slot is already negative, which is the unique signal that the current v is a duplicate. Because the constraints say each value appears once or twice, this correctly identifies every duplicate exactly once.
Hash-Set Variant (Fallback)
If the interviewer is fine with O(n) extra space, the hash-set version is harder to get wrong:
Complexity
Metric Negation Hash Set
Time O(n) O(n)
Extra Space O(1) O(n)
Mutates input? Yes NoPitfalls
- Forgetting
Math.abs. After negation,nums[i]may be negative, but the index it points to is still encoded by its magnitude. Readingnums[i]directly will produce an out-of-bounds index of-1or worse. - Modifying input is sometimes disallowed. If the interviewer adds the constraint "do not modify nums", the negation trick is off the table. Cycle detection (Floyd's) is the standard fallback for the single-duplicate variant; for the all-duplicates variant, fall back to the hash set.
- Off-by-one on the index. The index for value
visv - 1, notv. Skipping the subtraction puts the negation one slot too far right and silently breaks forv = n.
Solution Code