Find All Numbers Disappeared in an Array
Description
You get an array nums of n integers, where each nums[i] is in the range [1, n].
Return all the integers in the range [1, n] that do not appear in nums, in any order.
Follow-up: can you do it without extra space, in O(n) time? (The returned list doesn't count as extra space.)
Examples
Example 1
Input: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Output: [5,6]
Explanation: The values run from 1 to 8. 2 and 3 appear twice, which leaves no room for 5 and 6.
Example 2
Input: nums = [1, 1]
Output: [2]
Explanation: With n = 2 the values should be 1 and 2; 1 appears twice and 2 never does.
Constraints
- n == nums.length
- 1 ≤ n ≤ 10^5
- 1 ≤ nums[i] ≤ n
Editorial
Brute Force
Intuition
Check each value from 1 to n directly: scan the array for it. The ones you never find are missing.
Step-by-Step Explanation
Let's check every value for nums = [4, 3, 2, 7, 8, 2, 3, 1]:
- Scan for 1. It's at index 7, after 8 looks.
- Scan for 2. It's at index 2, after 3 looks.
- Scan for 3. It's at index 1, after 2 looks.
- Scan for 4. It's at index 0, after 1 look.
- Scan for 5. All 8 values checked, and 5 isn't there, so it's missing.
- Scan for 6. All 8 values checked, and 6 isn't there, so it's missing.
- Scan for 7. It's at index 3, after 4 looks.
- Scan for 8. It's at index 4, after 5 looks.
The missing values are [5, 6].
Scan for Every Value — Each step scans the array for one value; green marks where it was found.
Algorithm
- For each value
vfrom 1 to n: scannumsforv. - If it isn't found, add
vto the answer.
Code
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
int n = nums.size();
vector<int> missing;
for (int v = 1; v <= n; v++) // look for each value with a full scan
if (find(nums.begin(), nums.end(), v) == nums.end()) missing.push_back(v);
return missing;
}
};
class Solution:
def findDisappearedNumbers(self, nums: list[int]) -> list[int]:
return [v for v in range(1, len(nums) + 1) if v not in nums] # each `in` scans the list
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> missing = new ArrayList<>();
for (int v = 1; v <= nums.length; v++) { // look for each value with a full scan
boolean found = false;
for (int x : nums)
if (x == v) { found = true; break; }
if (!found) missing.add(v);
}
return missing;
}
}
var findDisappearedNumbers = function(nums) {
const missing = [];
for (let v = 1; v <= nums.length; v++) // look for each value with a full scan
if (!nums.includes(v)) missing.push(v);
return missing;
};
Complexity Analysis
Time Complexity: O(n²)
Each of the n values can scan all n entries.
Space Complexity: O(1) besides the answer
Why This Approach Is Not Efficient
At n = 10^5 that's up to 10^10 comparisons (over the time limit in Python, javascript).
A set of the values fixes the time (one lookup per value, O(n) in all) but costs O(n) extra memory, which the follow-up rules out. The way out is in the constraint: the values are 1 to n, and the array has n slots. Every value already has a slot of its own, so the array can record what's been seen.
Optimal Approach - Marking by Index
Intuition
Give each value v a home: index v − 1. For every value in the array, mark its home by making the number there negative. A sign holds one bit (seen or not), and the number itself survives, so you can still read it with abs when you get there.
When every value has marked its home, an index i that's still positive was never anybody's home: i + 1 never appeared.
Two details. Read each value with abs, because it may already have been marked. And set the sign, -abs(...), rather than flipping it: a value that appears twice would otherwise unmark its home.
Step-by-Step Explanation
Let's mark nums = [4, 3, 2, 7, 8, 2, 3, 1]:
- The values are 1 to 8, so value v has a home, index v − 1. Mark homes by making them negative.
- Index 0 holds 4 (sign ignored), so mark its home, index 3. It becomes -7.
- Index 1 holds 3 (sign ignored), so mark its home, index 2. It becomes -2.
- Index 2 holds 2 (sign ignored), so mark its home, index 1. It becomes -3.
- Index 3 holds 7 (sign ignored), so mark its home, index 6. It becomes -3.
- Index 4 holds 8 (sign ignored), so mark its home, index 7. It becomes -1.
- Index 5 holds 2 (sign ignored), so mark its home, index 1, which is already negative.
- Index 6 holds 3 (sign ignored), so mark its home, index 2, which is already negative.
- Index 7 holds 1 (sign ignored), so mark its home, index 0. It becomes -4.
- The homes still positive, 4 and 5, were never marked, so 5 and 6 never appeared.
Mark Each Value's Home — Each step reads a value (ignoring its sign) and makes its home index negative. The green indexes at the end were never marked.
Algorithm
- For each
xinnums: leti = |x| − 1and setnums[i] = −|nums[i]|. - Return every
i + 1wherenums[i]is still positive.
Code
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
for (int x : nums) {
int i = abs(x) - 1; // x may already be marked: read its absolute value
nums[i] = -abs(nums[i]); // mark "value i + 1 was seen"
}
vector<int> missing;
for (int i = 0; i < (int)nums.size(); i++)
if (nums[i] > 0) missing.push_back(i + 1); // never marked: i + 1 never appeared
return missing;
}
};
class Solution:
def findDisappearedNumbers(self, nums: list[int]) -> list[int]:
for x in nums:
i = abs(x) - 1 # x may already be marked: read its absolute value
nums[i] = -abs(nums[i]) # mark "value i + 1 was seen"
return [i + 1 for i, v in enumerate(nums) if v > 0]
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int x : nums) {
int i = Math.abs(x) - 1; // x may already be marked: read its absolute value
nums[i] = -Math.abs(nums[i]); // mark "value i + 1 was seen"
}
List<Integer> missing = new ArrayList<>();
for (int i = 0; i < nums.length; i++)
if (nums[i] > 0) missing.add(i + 1); // never marked: i + 1 never appeared
return missing;
}
}
var findDisappearedNumbers = function(nums) {
for (const x of nums) {
const i = Math.abs(x) - 1; // x may already be marked: read its absolute value
nums[i] = -Math.abs(nums[i]); // mark "value i + 1 was seen"
}
const missing = [];
for (let i = 0; i < nums.length; i++)
if (nums[i] > 0) missing.push(i + 1); // never marked: i + 1 never appeared
return missing;
};
Complexity Analysis
Time Complexity: O(n)
Two passes.
Space Complexity: O(1)
Besides the answer; the marks live in nums itself. (If the caller needs nums back, a third pass can make every number positive again.)
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Marking without abs. i = x - 1
On nums = [4, 3, 2, 7, 8, 2, 3, 1] it returns [2,5]; the answer is [5,6]. Once a value has been marked negative, x - 1 is negative too. Python's negative index then marks a slot counted from the end, silently. Read every value with abs.
Flipping the sign instead of setting it. nums[i] = -nums[i]
On nums = [2, 2] it returns [1,2]; the answer is [1]. A value that appears twice flips its home's sign twice, back to positive, and looks missing. Set the sign: -abs(nums[i]) is negative however many times it runs.
Returning the indexes. return [i for i, v in enumerate(nums) if v > 0]
On nums = [4, 3, 2, 7, 8, 2, 3, 1] it returns [4,5]; the answer is [5,6]. Index i is the home of the value i + 1. Return i + 1.
Using the sum of 1 to n. gap = n * (n + 1) // 2 - sum(set(nums))
On nums = [4, 3, 2, 7, 8, 2, 3, 1] it returns [11]; the answer is [5,6]. n(n + 1)/2 minus the sum of the distinct values gives the missing values' total, which names them only when exactly one is missing.
Where This Pattern Is Taught
This problem practises index marking, where the array is its own hash table. It's taught in Frequency Counting with Hash Maps.