1608. Special Array With X Elements Greater Than or Equal X

BS

T: O(nlogn)

S: O(1)

class Solution {
    public int specialArray(int[] nums) {
        Arrays.sort(nums);

        int left = 1;
        int right = nums[nums.length-1];
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (foundIt(mid, nums) == mid) {
                return mid;
            } else if (foundIt(mid, nums) > mid) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }
        return -1;
    }
    private int foundIt(int x, int[] nums) {
        int count = 0;
        for (int num : nums) {
            if (num >= x) {
                count++;
            }
        }
        return count;
    }
}

/**

count of x == (x <= nums[i])

0 0 3 4 4
   3

   2 100

   ans is 2

   1 100

   99 1000
 */

prefix sum idea

T: O(n)

S: O(n)

class Solution {
    public int specialArray(int[] nums) {
        int n = nums.length;
        int[] freq = new int[n+1];
        for (int i = 0; i < n; i++) {
            if (nums[i] >= n) {
                freq[n]++; // others count in n poistion
            } else {
                freq[nums[i]]++;
            }
        }
        int count = 0;
        for (int i = n; i >= 1; i--) {
            count += freq[i]; 
            if (count == i) { // count <= freq[i]
                return i;
            }
        }
        return -1;
    }
}

/**

0 1 2
    2

 */