Find All Numbers Disappeared in an Array
Given an array nums of n integers where each numsi is in the range [1, n], return an array of all the integers in that range that do not appear in nums. Since every value must fall between 1 and n, use each value as an index into the array itself — mark the position it points to as seen (for example, by flipping its sign) — so that any position never marked reveals a missing number, without extra memory.
Constraints
- n == nums.length
- 1 ≤ n ≤ 105
- 1 ≤ numsi ≤ n
Example
Input
nums = [4, 3, 2, 7, 8, 2, 3, 1]Output
[5, 6]Explanation 5 and 6 are the only numbers between 1 and 8 that never appear in nums.
In plain terms
- Index into the array itself
- Using a value from the array as a position within that same array, instead of storing seen values in a separate structure.
Mark visited positions by flipping the sign
04
13
22
37
48
52
63
71
Statusinit
value=4 -> mark index 3 negative.
What happens in this step
value = nums[0] = 4 target index = 4 - 1 = 3 Flip nums[3] to negative to mark 4 as seen.
Step 1 of 4
Steps to visualize
- Walk through nums; for each value v, compute the index v - 1.
- Make nums[v - 1] negative to mark that position as visited (if not already negative).
- After one pass, any index still holding a positive value means that index + 1 never appeared.
- Collect index + 1 for every position still positive.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
04
13
22
37
48
52
63
71
Statusinit
value=4 -> mark index 3 negative.
What happens in this step
value = nums[0] = 4 target index = 4 - 1 = 3 Flip nums[3] to negative to mark 4 as seen.
Step 1 of 4
Solution
function findDisappearedNumbers(nums) {
const arr = nums.slice();
for (let i = 0; i < arr.length; i++) {
const targetIndex = Math.abs(arr[i]) - 1;
if (arr[targetIndex] > 0) {
arr[targetIndex] = -arr[targetIndex];
}
}
const missing = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] > 0) {
missing.push(i + 1);
}
}
return missing;
}- Time
- O(n)
- Space
- O(1) extra (excluding the output array)
Test cases
| Input | Expected | Covers |
|---|---|---|
nums = [4, 3, 2, 7, 8, 2, 3, 1] | [5, 6] | example from the docstring |
nums = [1, 2, 3, 4] | [] | every number from 1 to n appears, nothing missing |
nums = [1, 1] | [2] | every element is the same value, most numbers missing |
nums = [1] | [] | smallest valid input, a single element with nothing missing |
nums = [3, 2, 1] | [] | values present but out of order, nothing missing |
nums = [2, 2, 2, 2] | [1, 3, 4] | multiple distinct numbers missing at once |