# Special Array With X Elements Greater Than or Equal X
**Difficulty:** EASY
[External](https://leetcode.com/problems/special-array-with-x-elements-greater-than-or-equal-x)
Canonical: https://scaleengineer.com/dsa/problems/special-array-with-x-elements-greater-than-or-equal-x
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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**.

**Example 1:**

**Input:** nums = [3,5]
**Output:** 2
**Explanation:** There are 2 values (3 and 5) that are greater than or equal to 2.

**Example 2:**

**Input:** nums = [0,0]
**Output:** -1
**Explanation:** No numbers fit the criteria for x.
If x = 0, there should be 0 numbers >= x, but there are 2.
If x = 1, there should be 1 number >= x, but there are 0.
If x = 2, there should be 2 numbers >= x, but there are 0.
x cannot be greater since there are only 2 numbers in nums.

**Example 3:**

**Input:** nums = [0,4,3,0,4]
**Output:** 3
**Explanation:** There are 3 values that are greater than or equal to 3.

**Constraints:**

* `1 <= nums.length <= 100`
* `0 <= nums[i] <= 1000`

# Approaches
## Brute Force Iteration
The most straightforward approach is to test every possible value for `x` and see if it meets the problem's criteria. The problem states that `x` is the number of elements greater than or equal to `x`. Since there are `n` elements in the array, the count of elements satisfying the condition can be at most `n`. Therefore, the value of `x` cannot be greater than `n`. This means we only need to check integers for `x` in the range `[0, n]`. For each candidate `x`, we can simply iterate through the entire `nums` array and count how many numbers are greater than or equal to `x`. If this count matches `x`, we've found our answer.
**Time:** O(n^2), where `n` is the number of elements in `nums`. The outer loop runs `n+1` times, and for each iteration, the inner loop runs `n` times. · **Space:** O(1), as we only use a few variables to store the count and loop indices.
**Pros:** Simple to understand and implement.; Requires no extra space, O(1) space complexity.
**Cons:** This approach is inefficient for larger arrays as it has a quadratic time complexity.; It repeatedly scans the entire array for each potential value of `x`.
### Explanation
This method involves a nested loop structure. The outer loop iterates through each possible candidate for the special number `x`, from `0` to the length of the array, `n`. The inner loop iterates through the `nums` array to count how many elements are greater than or equal to the current candidate `x`. If at any point the count equals `x`, we have found the unique special number and can return it immediately. If the outer loop completes without finding a match, it implies no such `x` exists, and we return -1.

```java
class Solution {
    public int specialArray(int[] nums) {
        int n = nums.length;
        for (int x = 0; x <= n; x++) {
            int count = 0;
            for (int num : nums) {
                if (num >= x) {
                    count++;
                }
            }
            if (count == x) {
                return x;
            }
        }
        return -1;
    }
}
```
### Algorithm
- Let `n` be the length of the `nums` array.
- Iterate through all possible values of `x` from `0` to `n`.
- For each `x`, we need to check if it satisfies the condition. To do this, we count the number of elements in `nums` that are greater than or equal to `x`.
- Initialize a counter, `count`, to 0.
- Iterate through the `nums` array. For each element `num`, if `num >= x`, increment `count`.
- After checking all elements in `nums`, if `count` is equal to `x`, we have found the special number. Return `x`.
- If the loop finishes without finding any such `x`, it means the array is not special. Return `-1`.

## Sorting and Linear Scan
We can improve the efficiency by sorting the array first. Once the array `nums` is sorted, we can more quickly determine how many elements are greater than or equal to a certain value. If a number `x` is the special number, it means there are exactly `x` elements in `nums` that are `>= x`. In a sorted array, these would be the last `x` elements. This observation allows us to check the condition in a single pass after the initial sort.
**Time:** O(n log n), dominated by the sorting step. The subsequent linear scan takes O(n) time. · **Space:** O(log n) to O(n), depending on the implementation of the sorting algorithm. For instance, Java's `Arrays.sort` for primitives uses a dual-pivot quicksort, which has an average space complexity of O(log n).
**Pros:** Significantly more efficient than the brute-force approach with O(n log n) time complexity.; The logic is sound and directly checks the necessary conditions on the sorted array.
**Cons:** The original array is modified due to sorting. If the original order must be preserved, a copy of the array is needed, which uses O(n) space.; Slightly more complex to reason about than the brute-force approach.
### Explanation
After sorting `nums` in ascending order, we can iterate through the array and check potential values for `x`. Let's say we are checking if `x` is the special number. In the sorted array, if the condition holds, the last `x` elements must be `>= x`, and the element at index `n-x-1` must be `< x`. We can formulate this into a single loop. We iterate `i` from `0` to `n-1`, and for each `i`, we test the candidate `x = n - i`. The `x` elements from `nums[i]` to `nums[n-1]` are the `x` largest elements. The condition `nums[i] >= x` ensures all of them are large enough. The condition `(i == 0 || nums[i-1] < x)` ensures that we have exactly `x` such elements. If we find such an `x`, we return it.

```java
import java.util.Arrays;

class Solution {
    public int specialArray(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        
        // Check possible values for x from n down to 1.
        // x = n - i
        for (int i = 0; i < n; i++) {
            int x = n - i;
            if (nums[i] >= x && (i == 0 || nums[i - 1] < x)) {
                return x;
            }
        }
        
        return -1;
    }
}
```
### Algorithm
- First, sort the input array `nums` in non-decreasing order.
- Let `n` be the length of the array.
- Iterate from `i = 0` to `n-1`. In each iteration, we consider a potential special number `x = n - i`. This `x` represents the count of elements from index `i` to the end of the sorted array.
- For `x` to be the special number, two conditions must be met:
  1. All these `x` elements must be greater than or equal to `x`. Since the array is sorted, we only need to check the smallest of them, which is `nums[i]`. So, `nums[i] >= x`.
  2. There must be *exactly* `x` such elements. This means the element just before this block, `nums[i-1]`, must be less than `x`. If `i` is 0, there is no preceding element, so this condition is implicitly met.
- If both `nums[i] >= x` and `(i == 0 || nums[i-1] < x)` are true, then `x` is the special number. Return `x`.
- If the loop completes without finding a solution, return -1.

## Frequency Counting
Given the constraints that `nums.length` is at most 100 and the values in `nums` are between 0 and 1000, we can use a counting-based approach for a highly efficient solution. This method avoids comparisons and sorting by directly counting the occurrences of each number. We can then use these counts to find the special number `x` in a single pass.
**Time:** O(N + M), where `N` is the length of `nums` and `M` is the range of values. We iterate through `nums` once (O(N)) and then through the frequency array once (O(M)). · **Space:** O(M), where `M` is the maximum possible value in `nums` (1001 in this case). This space is used for the frequency array.
**Pros:** This is the most efficient approach with a linear time complexity.; It's simple to implement and does not require complex data structures or algorithms like sorting.
**Cons:** Requires extra space proportional to the maximum possible value in the input array, which could be large if the constraints were different.
### Explanation
The core idea is to build a frequency map (or an array since the values are bounded) of the numbers in `nums`. We create an array `freq` of size 1001. `freq[i]` will store how many times the number `i` appears in `nums`. After populating this frequency array, we can determine the number of elements `>= x` for any `x`. A clever way to do this is to iterate `x` downwards from 1000 to 0. We maintain a running sum `count_ge` of elements greater than or equal to the current `x`. When we are at `x`, we add `freq[x]` to `count_ge`. Then, `count_ge` represents the total number of elements in `nums` that are `>= x`. We check if this `count_ge` is equal to `x`. If it is, we've found our answer. This approach processes the array in a way that gives us the counts we need with minimal repeated work.

```java
class Solution {
    public int specialArray(int[] nums) {
        // The maximum value for x is n, and the max value in nums is 1000.
        // We use a frequency array up to 1001.
        int[] freq = new int[1001];
        for (int num : nums) {
            freq[num]++;
        }

        int count_ge = 0; // count of numbers greater than or equal to x
        // Iterate x from the maximum possible value down to 0.
        for (int x = 1000; x >= 0; x--) {
            count_ge += freq[x];
            if (count_ge == x) {
                return x;
            }
        }

        return -1;
    }
}
```
### Algorithm
- Let `M` be the maximum possible value in `nums` plus one (e.g., 1001 based on constraints).
- Create a frequency array, `freq`, of size `M`, initialized to all zeros.
- Iterate through the input array `nums` and populate the frequency array: for each `num` in `nums`, increment `freq[num]`.
- Initialize a variable `count_ge = 0`, which will keep track of the number of elements greater than or equal to the current `x`.
- Iterate `x` downwards from `M-1` to `0`.
- In each step, add the frequency of the current number `x` to our running total: `count_ge += freq[x]`.
- After updating `count_ge`, it now holds the total count of numbers in the original array that are greater than or equal to `x`.
- Check if `count_ge == x`. If they are equal, we have found the special number, so return `x`.
- If the loop finishes and no such `x` is found, return -1.

# Solutions
### Java

```java
class Solution {
public
  int specialArray(int[] nums) {
    for (int x = 1; x <= nums.length; ++x) {
      int cnt = 0;
      for (int v : nums) {
        if (v >= x) {
          ++cnt;
        }
      }
      if (cnt == x) {
        return x;
      }
    }
    return -1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int specialArray(vector<int> &nums) {
    for (int x = 1; x <= nums.size(); ++x) {
      int cnt = 0;
      for (int v : nums)
        cnt += v >= x;
      if (cnt == x)
        return x;
    }
    return -1;
  }
};

```

### Python

```python
class Solution:
    def specialArray(self, nums: List[int]) -> int: for x in range(1, len(nums) + 1): cnt = sum(v >= x for v in nums) if cnt == x: return x return - 1

```