# 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…`