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…