Follow

# .css-ecb9sr{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-flex-direction:row;-ms-flex-direction:row;flex-direction:row;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;width:16rem;}  Follow # 448. Find All Numbers Disappeared in an Array

## An example of using vector<bool>

Nhut Nguyen
·Apr 25, 2022·

### 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: 
``````

#### Constraints

• `n == nums.length`.

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

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

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.

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”.