O(n) time and O(n) space well-commented solution in C++


#1

int Solution::solve(vector &A) {

// Make an array which stores number greater than them in the array. the size of this auxilarry array 
// is n+1. Also p can vary between 0 and size of input array(check for yourself).
int n = A.size();
if(n==1) return (A[0] == 0 ? 1: -1); // If size is 1, then 0 is answer for [0], otherwise no solution.
vector<int> gt(n+1,0);
int initial = n;
for(int i=0;i<n;i++){
    if(A[i] < n && A[i] >=0)gt[A[i]]++;
    else if(A[i] < 0) initial--; // takes care of negative numbers in array.
}

gt[0] = initial - gt[0]; // negative numbers taken care of
for(int i=1;i<=n;i++){
    if(gt[i] == 0) gt[i] = gt[i-1]; // if number does not exists in input array, take prev value.
    else gt[i] = gt[i-1] - gt[i]; // if number exists, subtract its occurings from last one.
}

//for(int i=0;i<=n;i++) cout <<i << " " << gt[i] << endl;

for(int i=0;i<=n;i++) if((gt[0] == 0) ||(gt[i] == i && gt[i]!= gt[i-1])) return 1;

return -1;

}