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);