Special Array With X Elements Greater Than or Equal X

easy search sorting counting

Problem

Given an array nums of non-negative integers, the array is special if there exists a value x such that exactly x elements of nums are greater than or equal to x. The value x need not appear in nums. Return that unique x if it exists, otherwise return -1.

Inputnums = [0,4,3,0,4]

Output3

Exactly 3 values (4, 3, 4) are greater than or equal to 3, so x = 3.

Inputnums = [0,0]

Output-1

No x works: x = 1 needs 1 element ≥ 1 but there are 0, x = 2 needs 2 but there are 0.

nums (comma-separated, 0..1000)

def special_array(nums):
    nums.sort(reverse=True)
    n = len(nums)
    for i in range(n):
        x = i + 1
        if nums[i] >= x and (i == n - 1 or nums[i + 1] < x):
            return x
    return -1

function specialArray(nums) {
  nums.sort((a, b) => b - a);
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    const x = i + 1;
    if (nums[i] >= x && (i === n - 1 || nums[i + 1] < x)) {
      return x;
    }
  }
  return -1;
}

int specialArray(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int x = i + 1;
        int v = nums[n - 1 - i];
        if (v >= x && (i == n - 1 || nums[n - 2 - i] < x)) {
            return x;
        }
    }
    return -1;
}

int specialArray(vector<int>& nums) {
    sort(nums.rbegin(), nums.rend());
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        int x = i + 1;
        if (nums[i] >= x && (i == n - 1 || nums[i + 1] < x)) {
            return x;
        }
    }
    return -1;
}

Explanation

We want a value x with exactly x elements ≥ x. The key trick is to sort the array in descending order. After sorting, the first i + 1 elements are the largest i + 1 values, so they are precisely the candidates for "the elements that are ≥ x" when x = i + 1.

For each index i (0-based) we test the candidate x = i + 1. There are exactly x = i + 1 elements at indices 0..i. For all of them to be ≥ x, it is enough that the smallest of them, nums[i], satisfies nums[i] ≥ x (the rest are larger because the array is sorted descending).

We also need that no extra element reaches x. The next element nums[i + 1] must be strictly less than x; otherwise there would be more than x elements ≥ x. If i is the last index there is no next element, so that condition is automatically satisfied.

When both checks pass we have found exactly x elements ≥ x, and the problem guarantees this x is unique, so we return it immediately. If the loop finishes without a match, no special value exists and we return -1.

The Java version sorts ascending (the built-in Arrays.sort has no descending option for primitives) and simply reads the array from the back: index n - 1 - i plays the role of nums[i] in the descending view. The logic is identical.

Sorting dominates the cost at O(n log n); the scan is a single linear pass over the sorted array.

Time: O(n log n) Space: O(1)