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.

Example 4:
Input: nums = [3,6,7,7,0]
Output: -1

 
Constraints:

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

Difficulty: introductory

Starter code:

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        

Solutions:
# class Solution:
#     def specialArray(self, nums: List[int]) -> int:
#         nums.sort(reverse=True)
#         left, right = 0, len(nums)
#         while left < right:
#             mid = left + (right - left) // 2
#             if mid < nums[mid]:
#                 left = mid + 1
#             else:
#                 right = mid       
#         return -1 if left < len(nums) and left == nums[left] else left
class Solution:
    def specialArray(self, a: List[int]) -> int:
        n, i = len(a), 0
        a.sort(reverse=True)        
        l, r  = 0, n
        while l < r:
            m = l + (r-l) // 2
            if m < a[m]:
                l  = m + 1
            else:
                r = m
        return -1 if l < n and l == a[l] else l


from bisect import bisect_left

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        
        nums.sort()
        l = len(nums)
        maxi = nums[-1]
        
        for i in range(maxi+1):
            if l - bisect_left(nums,i) == i:
                return i
        
        return -1

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        for i in range(0, len(nums)+1):
            if sum([n >= i for n in nums]) == i:
                return i
        return -1

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        
        res = -1
        
        
        nums.sort()
        
        for i in range(0, len(nums)):
            temp = 0
            for j in range(0, len(nums)):
                if nums[j] >= i+1 and nums[j] != 0:
                    temp += 1
                
            if i+1 == temp: 
                res = i+1 if i+1 > res else res
    
        return res


class Solution:
    def specialArray(self, nums: List[int]) -> int:
        # n --> length of given array
        n = len(nums)
        
        # temporary array with all elements 0
        temp = [0 for i in range(n)]
        
        # if all elements are 0 then given array is not special
        if nums==temp:
            return -1
        
        # check for each number from 0 to 1000 that for ith number there are exactly i numbers greater than or equal to i.
        for x in range(1001):
            cnt = 0
            for i in nums:
                if i>=x:
                    cnt+=1
            if cnt==x:
                return x
        return -1

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        x = 0
        res = 0
        maxn = max(nums)
        # minn = min(nums)
        for i in range(maxn+1):
            res = 0
            for y in nums:
                if y >= i:
                    res += 1
            if res == i:
                return i
        return -1


class Solution:
    def specialArray(self, nums: List[int]) -> int:
        for x in range(0, 1001):
            cnt = 0
            for e in nums:
                if e >= x:
                    cnt += 1
            if cnt == x:
                return x
        return -1

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        
        for x in range(-5, 1002):
            cnt = 0
            for y in nums:
                if y >= x:
                    cnt += 1
            if cnt == x:
                return x
        
        return -1

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        for i in range(1001):
            if sum(1 for a in nums if a >= i) == i:
                return i
        return -1


class Solution:
    def specialArray(self, nums: List[int]) -> int:
        for i in range(1, 1001):
            geq = 0
            for n in nums:
                geq += n >= i
            if geq == i:
                return i
        return -1

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        low, high = 0, len(nums)
        while low <= high:
            mid = (low + high) // 2
            cnt = 0
            for i in nums:
                if i >= mid: cnt += 1
            if cnt == mid:
                return mid
            elif cnt > mid: low = mid + 1
            else: high = mid - 1
        return -1

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        freq = collections.Counter()
        i, cnt = 1, 0
        for num in nums:
            freq[num] += 1
            if num >= i:
                cnt += 1
            if cnt == i:
                cnt -= freq[i]
                i += 1
        return -1 if cnt + freq[i-1] != i - 1 else i - 1


class Solution:
    def specialArray(self, nums: List[int]) -> int:
        cache=set()
        for x in range(len(nums),0,-1):
            cnt=0
            for i in range(len(nums)):
                if nums[i] in cache:
                    cnt+=1
                elif nums[i]>=x:
                    cnt+=1
                    cache.add(nums[i])
            if cnt==x:
                return x
        return -1

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        for x in range(len(nums), -1, -1):
            c = 0
            for n in nums:
                if n >= x:
                    c += 1
            if c == x:
                return x
            
        return -1

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        len_num = len(nums)
        for x in range(1, len_num+1):
            elem_greater = 0
            for num in nums:
                elem_greater += num >= x
            if x == elem_greater:
                return x
        return -1

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        for i in range(min(len(nums), max(nums)) + 1):
            if i == len([x for x in nums if x >= i]):
                return i
        return -1

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

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        x = None
        for i in range(1, len(nums) + 1):
            count = 0
            for n in nums:
                if n >= i:
                    count += 1
            if count == i:
                x = i
                break
        return x if x is not None else -1