Solution to Leetcode 1608: Special Array With X Elements Greater Than or Equal X

In this Leetcode problem, given an array nums we want to find an integer x such that there are exactly x elements in nums greater or equal to x.

You are given an array nums of non-negative integers. nums is considered special if there exists a number x such that there are exactly x numbers in nums that are greater than or equal to x.

Notice that x does not have to be an element in nums.

Return x if the array is special, otherwise, return -1. It can be proven that if nums is special, the value for x is unique.

One of the first thing we can notice is:

• If n is the size of the array vals, the solution, if it exists, must be between 1 and n.

Indeed, 0 can’t be a solution, because vals contains at least 1 element, and all elements of vals are greater or equal to 0.

Also, any number greater than n cannot be the solution because nums doesn’t contain enough elements to satisfy the condition then.

Solution 1: Sort the array

Sorting the array could help because at any point x in the array we know how many values are greater or equal to x. The only caveat is that we need to account for duplicates.

For instance, if the array is [0, 1, 1], if we check the second 1 (position 2), we might erroneously think there is only 1 element greater than 1. Therefore, only the first 1 (position 1) can be used to know how many elements are greater or equal than 1.

Because of the duplicates check, it is also a bit more difficult to be a binary search, so we will only go through the array linearly. The complexity will be dominated by the array sort anyways O(n lg n).

When we encounter a new value y in vals at index i, provided x = vals[i-1], we have:

• let p = n — i, if x < p <= y, then p is the solution.

Reversely, we can show that if these conditions are not satisfied, none of the p, x < p <= y is the solution of the problem.

We could also show the solution is unique, but that’s for another time.

We deduce the following code from the previous remarks:

class Solution {
    public int specialArray(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length…