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

Source: leetcode | Difficulty: EASY
Tags: Sorting

Data structures

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

Solutions:
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 = len(nums)
		temp = [0 for i in range(n)]
		if nums == temp:
			return -1
		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)
		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:
		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