An array is special if there is an x such that exactly x elements are greater than or equal to x. Return x or -1. It looks like a binary search problem, and it can be, but a counting pass is shorter and linear.
x can only be between 0 and n. Bucket each value into cnt[min(v, n)], then sweep x from n down to 0 keeping a running total of elements >= x. The first x where the total equals x is the answer, and it is unique.
def special_array(nums):
n = len(nums)
cnt = [0] * (n + 1)
for v in nums:
cnt[min(v, n)] += 1
total = 0
for x in range(n, -1, -1):
total += cnt[x]
if total == x:
return x
return -1
O(n) time and O(n) space. The sort plus binary search version is O(n log n).
Explain why x is unique: the count of elements >= x is non-increasing as x grows while x itself increases, so they can cross at most once.
The hard part of easy problems is explaining them crisply under time pressure. Practice narrating the approach, the complexity and one edge case in under a minute. Disclosure: I work on Linkjob AI, a real-time interview assistant. If you want live practice help, see AI interview copilot.