Find All Numbers Disappeared in an Array
Find All Numbers Disappeared in an Array: nums holds n integers in the range [1, n]. Return every value in that range that never appears, using O(1) extra space.
- n == nums.length
- 1 <= n <= 10⁵
- 1 <= nums[i] <= n
Intuition
Marking which values are present is the same sign-flipping trick the duplicates problem uses, but the question asked afterwards is the opposite one. After marking, a slot that is still positive was never visited, so the value it stands for — index + 1 — is missing. The answer is read from the absence of a mark rather than from encountering one, which is why the second pass matters as much as the first.
Values bounded by the array length plus an O(1) space requirement means the array is the storage. Whether you report the marks or the gaps decides which problem you are solving — this one reads the gaps. Missing Number and First Missing Positive are the neighbouring questions.
Approach
Before reading on: work out why a slot might be negated twice and what goes wrong without a guard. Then decide which pass actually produces the answer, and why it cannot be the first one.
Marking presence, then reading absence
Every value lies in [1, n], so value v owns index v - 1. In the first pass, negate nums[abs(v) - 1] for each element, marking that value as present. Nothing is reported during this pass. In the second, scan the indices: any slot still holding a positive number was never targeted, meaning no element equalled that index plus one. Collecting those index + 1 values gives the complete set of missing numbers, in ascending order for free since the scan runs left to right.
Why a slot may be negated more than once, and why it does not matter
Because values can repeat, the same index can be targeted twice. The first negation makes it negative; a second would make it positive again and corrupt the mark. Guarding with if nums[index] > 0 before negating — or equivalently assigning -abs(nums[index]) — makes the operation idempotent. This is the one real difference from the duplicates problem, where the second visit is precisely the signal being detected; here it must be suppressed.
Cost, and restoring the array
Two linear passes give O(n) time, and the only storage is the output list, which the problem excludes from the space bound — so extra space is O(1). The input is left with negated entries; if the caller needs it intact, a third pass taking absolute values restores it exactly, since the magnitudes were never altered. A hash set of seen values would be simpler to write but costs O(n) space and is what the follow-up rules out.
Solution & live demo
Common pitfalls
Negating without a guard
nums[index] = -nums[index]
if nums[index] > 0:
nums[index] = -nums[index]A repeated value targets the same index twice, and the second negation flips it back to positive. That slot is then wrongly reported as missing — [1,1,2] would claim 1 is absent.
Reporting during the first pass
for num in nums:
if nums[abs(num) - 1] > 0:
result.append(...)mark in pass one, collect in pass two
Absence can only be established once every element has been examined. A value not yet reached in the first pass would be wrongly reported as missing.
Collecting nums[i] instead of i + 1
result.append(nums[i])
result.append(i + 1)
The surviving positive value is whatever the input happened to store there, not the missing number. The missing value is encoded by the position: i + 1.
Edge cases
Every slot is negated, and the second pass returns an empty list.
Only index 0 is marked, so 2 and 3 are reported missing.
Index 0 is marked and nothing is missing.
The guard keeps the slot negative rather than flipping it back to positive.
abs() recovers the original value, so the index stays correct.