Follow

# Nhut Nguyen

Follow # C++ Solution to Coding Challenge 448. Find All Numbers Disappeared in an Array

Nhut Nguyen
·Nov 24, 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: Marking the appearances

``````#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: `O(logN)` (`vector<bool>` is optimized for space efficiency).

### References

Get my FREE book "10 Classic Coding Challenges"