# 448. Find All Numbers Disappeared in an Array

## An example of using vector<bool>

### Problem statement

Given an array `nums`

of `n`

integers where `nums[i]`

is in the range `[1, n]`

, return an array of all the integers in the range `[1, n]`

that do not appear in `nums`

.

#### Example 1

```
Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]
```

#### Example 2

```
Input: nums = [1,1]
Output: [2]
```

#### Constraints

`n == nums.length`

.`1 <= n <= 10^5`

.`1 <= nums[i] <= n`

.

#### Follow up

Could you do it without extra space and in `O(n)`

runtime? You may assume the returned list does not count as extra space.

### Solution 1: Marking the appearances

You can use a vector of `bool`

to mark which value appeared in the array.

#### Code

```
#include <vector>
#include <iostream>
using namespace std;
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<bool> exist(nums.size() + 1, false);
for (auto& i : nums) {
exist[i] = true;
}
vector<int> result;
for (int i = 1; i <= nums.size(); i++) {
if (!exist[i]) {
result.push_back(i);
}
}
return result;
}
void print(vector<int>& nums) {
cout << "[";
for (auto& n : nums) {
cout << n << ",";
}
cout << "]\n";
}
int main() {
vector<int> nums = {4,3,2,7,8,2,3,1};
auto result = findDisappearedNumbers(nums);
print(result);
nums = {1,1};
result = findDisappearedNumbers(nums);
print(result);
}
```

```
Output:
[5,6,]
[2,]
```

#### Complexity

Runtime:

`O(n)`

, where`n = nums.length`

.Extra space: much less than

`O(n)`

.`vector<bool>`

is optimized for space efficiency; it stores single bits.

### Solution 2: Follow up

You could use the indices of the array `nums`

to mark the appearances of its elements because they are identical (`[1, n]`

vs. `[0, n-1]`

).

One way of marking the appearance of an index `j`

is making the element `nums[j]`

to be negative. Then the indices `j`

's whose `nums[j]`

are unchanged (still positive) are the ones that do not appear in `nums`

.

#### Code

```
#include <vector>
#include <iostream>
using namespace std;
vector<int> findDisappearedNumbers(vector<int>& nums) {
int j;
for (int i{0}; i < nums.size(); i++) {
j = abs(nums[i]);
nums[j - 1] = -abs(nums[j - 1]);
}
vector<int> result;
for (int i{1}; i <= nums.size(); i++) {
if (nums[i - 1] > 0) {
result.push_back(i);
}
}
return result;
}
void print(vector<int>& nums) {
cout << "[";
for (auto& n : nums) {
cout << n << ",";
}
cout << "]\n";
}
int main() {
vector<int> nums = {4,3,2,7,8,2,3,1};
auto result = findDisappearedNumbers(nums);
print(result);
nums = {1,1};
result = findDisappearedNumbers(nums);
print(result);
}
```

```
Output:
[5,6,]
[2,]
```

#### Complexity

Runtime:

`O(N)`

, where`N = nums.length`

.Extra space:

`O(1)`

(the returned list does not count as extra space).

### Conclusion

Solution 2 helps to avoid allocating extra memory but it is not straightforward to understand.

Though Solution 1 requires some extra space, that memory is not much since

`vector<bool>`

is optimized for space efficiency. Moreover, it is easier to understand than Solution 2.

*What is your approach? The problem was picked from* *leetcode.com**, where you can submit your solution in any programming language and check the performance.*

*Thanks for reading. Feel free to share your thought about my content and check out my* *FREE book “10 Classic Coding Challenges”**.*