#442
Find All Duplicates in an Array
Medium Index marking
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Values are in 1..n and each appears once or twice. Return every value that appears twice, in O(n) time and O(1) extra space.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: values 1..n, some appear twice — list them.
Why this works: visiting value v flips nums[v-1] negative. If it's already negative, we've seen v before.
Example: [4, 3, 2, 7, 8, 2, 3, 1]
4,3,2,7,8 mark their slots2 again → slot 1 already negative → duplicate 23 again → slot 2 already negative → duplicate 3
✦Hints open one at a time
Same marking trick as "numbers disappeared": value v points to index v - 1.
If the slot is already negative when you visit it, you've seen v before.
↗Approach
For each value v = |nums[i]|, look at nums[v - 1]. If it's negative, v is a duplicate; otherwise negate it.
</>Solution (Java)
import java.util.*;
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int v = Math.abs(nums[i]);
if (nums[v - 1] < 0) ans.add(v); // second visit
else nums[v - 1] = -nums[v - 1];
}
return ans;
}
}!Common mistake
Forgetting Math.abs when reading a value that was already negated.
Complexity
- Time: O(n).
- Space: O(1) extra.
Topic: Arrays
