💬 Discord
Sign In
NeetCode #87LC-1608EasyArrays & Hashing
← Back to All Problems

#87 · #1608 · Special Array With X Elements Greater Than or Equal X(特殊数组的特征值)

📌 Problem Statement & Constraints

An array is special if there exists a number x such that exactly x elements in the array are greater than or equal to x. Given nums, return x, or -1 if no such value exists. If multiple x satisfy the condition, the answer is guaranteed unique. Constraints: 1 <= nums.length <= 100, 0 <= nums[i] <= 1000.

💡 Core Algorithmic Approaches

  1. Sort the array, then for a candidate x the count of elements >= x is n - lower_bound(x).
  2. Check candidates from n down to 1; the first one satisfying count == x is the answer.
  3. Binary search (bisect_left) gives the lower bound in O(log n), so each candidate costs O(log n).
  4. Iterating x from n downward is required because x cannot exceed n (there are only n elements) and the largest valid x is the answer when the statement guarantees uniqueness.

💻 Benchmark Python3 Implementation

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        from bisect import bisect_left
        nums.sort()
        n = len(nums)
        for x in range(n, 0, -1):          # x cannot exceed n
            cnt = n - bisect_left(nums, x)  # elements >= x
            if cnt == x:
                return x
        return -1


# Linear alternative: sort descending and scan
class Solution2:
    def specialArray(self, nums: List[int]) -> int:
        nums.sort(reverse=True)
        for i in range(len(nums)):
            if nums[i] >= i + 1 and (i + 1 == len(nums) or nums[i + 1] < i + 1):
                return i + 1
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n) for the sort plus O(n log n) for the candidate loop in the first version, or O(n) after sorting in the second.
💾 Space Complexity
O(1) beyond the in-place sort.

⚠️ Interview Pitfalls & Follow-ups

  • Iterating x from 1 upward and returning the first match: that yields the smallest valid x, but the problem asks for the answer when it is unique -- iterating downward is the safe convention and matches the expected output when several candidates exist.
  • Using bisect_right: the count of elements >= x uses bisect_left(nums, x); bisect_right counts elements > x.
  • Considering x = 0: zero elements greater than or equal to 0 is false whenever the array is non-empty, so 0 is never a valid answer.
  • Allowing x > n: impossible, since there are only n elements.