Follow

Follow
448. Find All Numbers Disappeared in an Array

448. Find All Numbers Disappeared in an Array

An example of using vector<bool>

Nhut Nguyen's photo
Nhut Nguyen
·Apr 25, 2022·

2 min read

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: 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(1) (vector<bool> is optimized for space efficiency).

References

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

Did you find this article valuable?

Support LeetSolve by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this