358. Find All Duplicates in an Array
You receive an integer array nums of length n whose values all sit in the range [1, n], and every value occurs either once or twice — never more.
Return a list of every value that occurs twice, ordered by where its second occurrence appears in nums (left to right). If nothing repeats, return an empty list.
The follow-up that interviewers care about: can you find them in O(n) time while using only constant extra memory beyond the returned list? The value range [1, n] is the giveaway.
Example 1:
Input: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Output: [2, 3]
Explanation: 2 shows up at indices 2 and 5, and 3 shows up at indices 1 and 6. Their second occurrences land at indices 5 and 6, so 2 is reported before 3.
Example 2:
Input: nums = [1, 1, 2]
Output: [1]
Explanation: Only the value 1 appears twice; 2 appears once.
Example 3:
Input: nums = [1]
Output: []
Explanation: A single element can never repeat, so the answer is an empty list.
Constraints:
- 1 ≤ n = nums.length ≤ 10⁵
- 1 ≤ nums[i] ≤ n
- Every value appears once or twice.
Hints:
A hash set of values you have already seen finds every second occurrence in one pass — that is O(n) time but also O(n) extra space.
Every value v is a valid index v − 1 into the array itself. Can the array double as its own "seen" table?
Flip nums[v − 1] negative the first time you meet v. If it is already negative when you arrive, this is v's second visit.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Expected output: [2, 3]