LeetCode 1608: Special Array With X Elements Greater Than or Equal X

Explanation

To solve this problem, we can follow these steps:

1. Sort the input array nums in non-decreasing order.
2. Iterate over the sorted array and for each element nums[i], check if there are exactly n - i elements greater than or equal to nums[i].
3. If such an element nums[i] is found, return n - i.
4. If no such element is found after the iteration, return -1.

Time complexity: O(n log n) due to sorting the input array
Space complexity: O(1)

import java.util.Arrays;

class Solution {
    public int specialArray(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] >= n - i) {
                if (i == 0 || nums[i - 1] < n - i) {
                    return n - i;
                }
            }
        }
        return -1;
    }
}