Special Array With X Elements Greater Than or Equal X

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.

Examples

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

Solution

Method 1 - Sorting

We saw in example 1, that even though 2 was not in the array, there exists x=2 where there are 2 values which are greater than x=2. Suppose, we have input nums = [2], then x = 1. ⇨ So, this x is between 1 and n, where n is the length of the array.

So, sorting the elements(say in ascending order) can help us. Also, in eg 1, we see that array is sorted, and nums[0] > n, so n is the answer.

Video explanation

Here is the video explaining this method in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/qxZ0I8TbZ7c" frameborder="0" allowfullscreen></iframe></div>

Algorithm

Lets look at example 3 for this.

1. Sort the array ([0,4,3,0,4] ⇨ [0,0,3,4,4])
2. Now, iterate on array with iterator say x from 1 to n (n = 5). Now, we try to find the pivot point from the end of the array such that nums[pivot] >= x and nums[pivot - 1] < x. Lets call this element possible candidate.
   1. Define a candidate position in array as n - x (we know that for x=3 there should be 3 numbers in range, lets say x=3, our candidate position is 5-3 = 2)
   2. If value of candidate is >= x and previous number is < x - we found x: nums[candidate] = 3 >= 3 and nums[candidate-1] = 0 < 3.
   3. So, we found our X.

Why use n-x?

Here's how n - x works with respect to x:

• Since n is the total number of elements in the array, n - 1 would be the index of the last element
• If we're looking for exactly x elements that are greater than or equal to x, that means there are n - x elements that are less than x.
• Therefore, n - x signifies the starting point (index) where we expect to find elements that are greater than or equal to x. In other words, if x is the special number, nums[n - x] should be greater than or equal to x, and nums[n - x - 1] should be less than x (since it's the first element that isn't part of the x elements greater than or equal to x).

With the array sorted in non-decreasing order, this means that at index n - x we transition from elements less than x to elements that are at least x or more, where x is the candidate for our "special" number. If we find that the element at index n - x is indeed greater than or equal to x and the one right before it (at index n - x - 1) is less than x, then x fits the definition of the "special" number, and we have found our answer.

Visualization

Let array be:
index =   0   1   2   3   4
nums  = | 1 | 2 | 3 | 4 | 5 |
n = 5

Lets see some values of x and candidates:

x = 1

x = 1, candidate = n - x => 4; nums[candidate] = 5

nums  = | 1 | 2 | 3 | 4 | 5 |
          ^               ^
          x              n-x

x = 2

x = 2, candidate = n - x => 3; nums[candidate] = 4

nums  = | 1 | 2 | 3 | 4 | 5 |
              ^       ^
              x      n-x

x = 3

x = 3, candidate = n - x => 2; nums[candidate] = 3

nums  = | 1 | 2 | 3 | 4 | 5 |
                  ^  
                  x
				 n-x

Clearly x = 3 is our answer, as n-x is the right pivot points.

Code

Java

class Solution {

	public int specialArray(int[] nums) {
		Arrays.sort(nums);
		int n = nums.length;

		if (nums[0] >= n) {
			return n;
		}

		for (int x = 1; x <= n; x++) {
			int candidate = n - x;

			if (nums[candidate] >= x && nums[candidate - 1] < x) {
				return x;
			}
		}

		return -1;
	}
}

Complexity

• ⏰ Time complexity: O(n log n) (O(nlogn) for sorting, and O(n) for going through sorted array)

• 🧺 Space complexity: O(1)

Method 2 - Using Counting sort

Code

class Solution {

	public int specialArray(int[] nums) {
		bucketSort(nums);
		int n = nums.length;

		if (nums[0] >= n) {
			return n;
		}

		for (int x = 1; x <= n; x++) {
			int candidate = n - x;

			if (nums[candidate] >= x && nums[candidate - 1] < x) {
				return x;
			}
		}

		return -1;
	}

	private void bucketSort(int[] nums) {
        int numBuckets = 1001; 

        int[] buckets = new int[numBuckets];

        for (int num : nums) {
            buckets[num]++;
        }

        int index = 0;
        for (int i = 0; i < numBuckets; i++) {
            // Add the elements from each bucket back to the original array
            for (int j = 0; j < buckets[i]; j++) {
                nums[index++] = i;
            }
        }
    }

}

Complexity

• ⏰ Time complexity: O(n) (O(n) for sorting and O(n) for iterating on nums).
• 🧺 Space complexity: O(1) (For bucket sort we use O(1001) space, i.e. O(1))