Easy to understand O(n) solution C++


#1

int Solution::solve(vector& arr) {
int n = arr.size();
vector eq(n+1), gt(n+1);
// eq[i] is the number of values equal to than i, for 0 <= i < n
// but eq[n] is the number of values greater or equal to n
// gt[i] is number of values greater than i, for 0 <= i < n, gt[n] is 0.
for (int i : arr) {
if (i >= 0 && i < n) {
eq[i]++;
} else if (i >= n) {
eq[n]++;
}
}
for (int i=n-1; i>=0; iā€“) {
gt[i] = gt[i+1] + eq[i+1];
}
for (int i=0; i<n; i++) {
if (gt[i] == i && eq[i] > 0) {
return 1;
}
}
return -1;
}