Follow

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: [2]

#### 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"

### Did you find this article valuable?

Support Nhut Nguyen by becoming a sponsor. Any amount is appreciated!