361. Find All Numbers Disappeared in an Array
You receive an integer array nums of length n where every value lies in the range [1, n]. Some values from that range may appear multiple times, which forces other values to be absent entirely.
Return every integer in [1, n] that never appears in nums, in increasing order. If every value from 1 to n is present, return an empty list.
The follow-up: do it in O(n) time using no extra space beyond the returned list — the [1, n] value range makes the array itself big enough to keep the books.
Example 1:
Input: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Output: [5, 6]
Explanation: n = 8, so the full range is 1..8. The values 2 and 3 each appear twice, crowding out 5 and 6, which never appear.
Example 2:
Input: nums = [1, 1]
Output: [2]
Explanation: n = 2 and the range is 1..2. Both slots hold 1, so 2 is missing.
Example 3:
Input: nums = [3, 2, 1]
Output: []
Explanation: Every value in 1..3 shows up, so nothing is missing.
Constraints:
- 1 ≤ n = nums.length ≤ 10⁵
- 1 ≤ nums[i] ≤ n
Hints:
Collect the values that DO appear into a hash set, then walk 1..n and report every value the set lacks. That is O(n) time but O(n) extra space.
To drop the set: each value v owns slot v − 1 of the array itself. Can you leave a mark in a slot without losing the number stored there?
Negate nums[v − 1] when you see v (use absolute values when reading). Afterwards, any slot still positive belongs to a value nobody visited.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Expected output: [5, 6]