Description

Submission

class Solution {
public:
    int specialArray(vector<int>& nums) {
        sort(nums.begin(), nums.end(), greater<int>());
        
        for(int i = 0; i < nums.size(); ++i) {
            int n = i + 1;
            if(nums[i] >= n &&((i+1 == nums.size()) || (i+1 < nums.size() && nums[i+1] < n))) {
                return n;
            }
        }
        return -1;
    }
};

Submission 211129

class Solution {
    int count(vector<int>& nums, int x) {
        // find the number of values that are >= x
        int cnt = 0;
        for(int num: nums) {
            if(num >= x) ++cnt;
        }    
        return cnt;
    }
public:
    int specialArray(vector<int>& nums) {
        int lower = 0, upper = nums.size();

        while(lower < upper) {
            int mid = upper - (upper - lower) / 2;

            if(count(nums, mid) < mid) {
                // mid is too large
                upper = mid - 1;
            } else {
                lower = mid;
            }
        }

        if(count(nums, lower) == lower) return lower;
        return -1;
    }
};

// [0,4,3,0,4]
// 0 0 3 4 4

// [0,5,0,1,8,3,0,1]
// 0 0 0 1 1 3 5 8