1608. Special Array with X Elements Greater than or Equal X - Explanation

1. Brute Force

Intuition

We need to find a value x such that exactly x elements in the array are greater than or equal to x. The simplest approach is to try every possible value of x from 1 to n (the array length) and count how many elements satisfy the condition. If we find a match, we return that value. Since x must equal the count, x cannot exceed n (we can have at most n elements).

Algorithm

Iterate through each candidate value i from 1 to n.
For each candidate, count how many elements in the array are greater than or equal to i.
If the count equals i, return i as the special value.
If no valid value is found after checking all candidates, return -1.

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

            if cnt == i:
                return i

        return -1

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Binary Search

Intuition

Instead of checking every value linearly, we can use binary search on the answer. The key observation is that as x increases, the count of elements greater than or equal to x decreases (or stays the same). This monotonic property allows us to binary search for the special value. If the count is less than mid, we need a smaller x. If the count is greater than mid, we need a larger x.

Algorithm

Set search bounds: l = 1 and r = n (the array length).
While l <= r:
- Calculate mid = (l + r) / 2.
- Count elements greater than or equal to mid.
- If count equals mid, return mid.
- If count is less than mid, search the lower half by setting r = mid - 1.
- Otherwise, search the upper half by setting l = mid + 1.
Return -1 if no special value exists.

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        l, r = 1, len(nums)
        while l <= r:
            mid = (l + r) >> 1
            cnt = sum(1 for num in nums if num >= mid)

            if cnt == mid:
                return mid

            if cnt < mid:
                r = mid - 1
            else:
                l = mid + 1

        return -1

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$

3. Sorting

Intuition

After sorting the array, we can efficiently determine how many elements are greater than or equal to any value. For each position i in the sorted array, there are n - i elements from index i to the end. We scan through the array and check if totalRight (the count of remaining elements) could be the special value. A valid special value must fall within a valid range defined by consecutive distinct elements.

Algorithm

Sort the array in ascending order.
Initialize totalRight = n (all elements to the right including current).
Traverse the sorted array:
- If nums[i] equals totalRight, or totalRight falls strictly between prev and nums[i], return totalRight.
- Skip duplicate elements.
- Update prev and move to the next distinct element, updating totalRight.
Return -1 if no special value is found.

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        nums.sort()
        i = 0
        prev = -1
        total_right = len(nums)
        while i < len(nums):
            if nums[i] == total_right or (prev < total_right < nums[i]):
                return total_right

            while i + 1 < len(nums) and nums[i] == nums[i + 1]:
                i += 1

            prev = nums[i]
            i += 1
            total_right = len(nums) - i

        return -1

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

4. Sorting + Two Pointers

Intuition

After sorting, we use two pointers: one for the candidate value j and another for the array index i. As we increase j, the number of elements greater than or equal to j can only decrease. We advance i to skip elements smaller than the current candidate and check if the remaining count matches j.

Algorithm

Sort the array in ascending order.
Initialize i = 0 (array pointer) and j = 1 (candidate value).
While both pointers are within valid bounds:
- Advance i past all elements smaller than j.
- If the count of remaining elements (n - i) equals j, return j.
- Increment j to try the next candidate.
Return -1 if no special value exists.

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        i, j = 0, 1

        while i < n and j <= n:
            while i < n and j > nums[i]:
                i += 1

            if j == n - i:
                return j
            j += 1

        return -1

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

5. Counting Sort

Intuition

We can use a counting array to track how many elements have each value. Since any element greater than n is effectively the same as n for our purposes (they all contribute to counts for candidates 1 through n), we cap values at n. By iterating from the largest possible candidate down to 0 and accumulating counts, we can efficiently find when the running total equals the current index.

Algorithm

Create a count array of size n + 1.
For each element, increment count[min(num, n)].
Traverse from index n down to 0, accumulating the count in totalRight.
If at any index i, totalRight equals i, return i as the special value.
Return -1 if no match is found.

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        count = [0] * (len(nums) + 1)
        for num in nums:
            index = min(num, len(nums))
            count[index] += 1

        total_right = 0
        for i in range(len(nums), -1, -1):
            total_right += count[i]
            if i == total_right:
                return total_right
        return -1

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Searching Beyond Array Length

The special value x cannot exceed n (the array length) since there are at most n elements. Searching for values greater than n is unnecessary and can lead to incorrect results or wasted computation.

Using Strict Greater Than Instead of Greater Than or Equal

The problem requires counting elements greater than or equal to x, not strictly greater than. Using the wrong comparison operator will lead to incorrect counts and potentially return -1 when a valid answer exists, or return an incorrect special value.