LC 448. Find All Disappear numbers in an Array

Nilanjan Deb · April 1, 2020

This is a easy question. It can Easily done by using Brute force method. But It crossed time limit. I first try it by brute force method as Time limit exceeded, So I tried for a better approach. First I remove all duplicates. Then start traversing over it if difference of consecutive terms greater than 1, then I push the missing element to the answer and so on. Remainings are Self understandable. Don’t forget about corner cases.

This is my CPP solution.

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        if(n==0){
            return nums;
        }
        sort(nums.begin(),nums.end());
        vector<int>ans;
        int j = 0;
        for(int i=0;i<n-1;i++){
            if(nums[i]!=nums[i+1]){
                nums[j++] = nums[i];
            }
        }
        nums[j++] = nums[n-1];
        for(int i=0;i<j;i++){
            cout << nums[i] << ' ';
        }
        if(nums[0] - 1 != 0){
                int dif = nums[0] - 2;
                while(dif>=0){
                    ans.push_back(1 + dif);
                    dif--;
                }
            }
        for(int i=0;i<j-1;i++){
            if(nums[i+1]-nums[i]!=1){
                int dif = nums[i+1] - nums[i] - 1;
                while(dif){
                    ans.push_back(nums[i]+dif);
                    dif--;
                }
            }
        }
        if(n - nums[n-1] != 0){
                int dif = n - nums[n-1];
                while(dif){
                    ans.push_back(nums[n-1]+dif);
                    dif--;
                }
            }
        return ans;
    }
};

Time Complexity O(n);



Dicussion Forum