Find All Duplicates in an Array
Problem
An array of length n holds values in the range 1 to n, and each value appears once or twice. Return all values that appear twice, using linear time and only constant extra space besides the output.
Examples
Constraints
- • 1 <= n <= 10^5
- • 1 <= nums[i] <= n
- • Each value appears at most twice
Hints & approach
Hint 1
Values are in 1..n, so each value can be mapped to an index.
Hint 2
You can leave a mark at that index without losing the value stored there.
Hint 3
Flip the sign of nums[v - 1] when you see v; if it is already negative, v is a repeat.
Approachtry the hints first
Use the array itself as a visited set. For each value v (take its absolute value, since earlier steps may have negated it), look at index v - 1. If nums[v - 1] is already negative, v was seen before, so add it to the result; otherwise negate nums[v - 1] to mark v as seen. The sign bit acts as a free boolean flag per value.
Time O(n) · Space O(1) extra