# 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 consideredspecialif there exists a number`x`

such that there areexactly`x`

numbers in`nums`

that aregreater than or equal to`x`

.Notice that

`x`

does nothave to be an element in`nums`

.Return

`x`

if the array isspecial, otherwise, return`-1`

. It can be proven that if`nums`

is special, the value for`x`

isunique.

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…