Special Array With X Elements Greater Than Or Equal X - Leetcode Solution

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 are greater than or equal to 2 and hence, no "x" exists in the array.

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:

The brute force approach of solving this problem will be to iterate over all possible values of x - from 1 to the maximum element in the array and for each value of x, count the number of elements in the array that are greater than or equal to x. If the count is equal to x, then we have found our answer and we can return x. However, this approach will have a time complexity of O(n^2) as we have to iterate over all possible values of x for each element in the array.

A more efficient approach will be to sort the array in non-increasing order and then look for the first position where the number at that index is less than or equal to the count of the remaining elements in the array. For example, let's say we have an array [4,3,2,1,0]. After sorting the array, it becomes [4,3,2,1,0]. Now we start checking from the first element, 4. There are 4 elements after 4 in the sorted array i.e., [3,2,1,0]. Since 4 is greater than the count of the remaining elements i.e., 4, we move to the next element, 3. There are 3 elements after 3 i.e., [2,1,0]. Since 3 is greater than the count of the remaining elements i.e., 3, we move to the next element, 2. There are 2 elements after 2 i.e., [1,0]. Since 2 is equal to the count of the remaining elements i.e., 2, we have found our answer and we return 2.

If we do not find any such index, then we return -1.

Time Complexity:

The time complexity of this approach is O(nlogn) as we are sorting the array which takes O(nlogn) time complexity and then iterating over the sorted array which takes O(n) time complexity.

Space Complexity:

The space complexity of this approach is O(1) as we are not using any extra space.

Code:

class Solution: def specialArray(self, nums: List[int]) -> int: nums.sort(reverse=True) n = len(nums) for i in range(n): if nums[i] <= i: if i == 0 or nums[i-1] > i: return i return -1

1