LeetCode 1608 - Special Array With X Elements Greater Than or Equal X

The problem gives us an array nums containing non-negative integers. We need to determine whether there exists an intege

leetcodeeasyarraybinary-searchsorting

LeetCode Problem 1608

Difficulty: 🟢 Easy
Topics: Array, Binary Search, Sorting

Solution

Problem Understanding

The problem gives us an array nums containing non-negative integers. We need to determine whether there exists an integer x such that exactly x elements in the array are greater than or equal to x.

The important detail is that x does not need to appear inside the array itself. We are only concerned with the count of elements satisfying the condition.

For example, if nums = [3,5], then there are exactly two numbers greater than or equal to 2, namely 3 and 5. Therefore, the array is special and the answer is 2.

If no such integer exists, we return -1.

The constraints are relatively small:

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

Since the array size is at most 100, even quadratic algorithms are acceptable. However, there is still value in designing a clean and efficient solution.

There are several edge cases that can easily cause mistakes:

  • Arrays containing only zeros, such as [0,0]
  • Arrays where multiple candidate values appear possible at first glance
  • Arrays with repeated values
  • Cases where the valid x is not present in the array
  • Very small arrays, especially arrays of length 1

The problem guarantees that if a valid x exists, it is unique. This means we do not need to handle multiple valid answers.

Approaches

Brute Force Approach

The most direct solution is to try every possible value of x.

Since the array length is n, the number of elements greater than or equal to x can never exceed n. Therefore, we only need to test values from 0 to n.

For each candidate x:

  1. Traverse the array
  2. Count how many elements are greater than or equal to x
  3. Check whether the count equals x

If we find a match, we return x. Otherwise, after testing all possibilities, we return -1.

This approach is correct because it explicitly checks the definition of a special array for every possible candidate.

The time complexity is O(n^2) because for each candidate x, we scan the entire array.

Optimal Approach

A better solution comes from sorting the array.

After sorting in ascending order, we can reason about how many elements are greater than or equal to a particular value.

Suppose the sorted array is:

a[0], a[1], a[2], ..., a[n-1]

At index i, there are exactly n - i elements from a[i] to the end of the array.

If:

a[i] >= n - i

then at least n - i elements are large enough.

However, we also need to ensure that exactly n - i elements satisfy the condition. That means the previous element must be smaller than n - i.

Formally:

a[i] >= n - i
and
a[i - 1] < n - i

If both conditions hold, then x = n - i.

Sorting allows us to compute the answer in a single linear scan after sorting.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Tries every possible x and counts qualifying elements
Optimal O(n log n) O(1) or O(log n) Sorts the array and uses index relationships

Algorithm Walkthrough

Optimal Sorting Algorithm

  1. Sort the array in non-decreasing order.

Sorting groups smaller values at the beginning and larger values at the end. This makes it easy to determine how many elements are greater than or equal to a threshold. 2. Let n be the length of the array.

If we are currently examining index i, then there are exactly n - i elements from index i through the end of the array. 3. Iterate through the sorted array from left to right.

For each position i, compute:

candidate = n - i

This represents the number of elements remaining in the suffix. 4. Check whether the current value supports this candidate.

We need:

nums[i] >= candidate

because all elements from i onward must be at least candidate. 5. Ensure the previous element does not also satisfy the condition.

If i > 0, we also require:

nums[i - 1] < candidate

This guarantees that exactly candidate elements qualify, not more. 6. If both conditions are true, return candidate. 7. If the loop finishes without finding a valid candidate, return -1.

Why It Works

After sorting, the suffix starting at index i contains exactly n - i elements. If the smallest element in that suffix is at least n - i, then every element in the suffix also satisfies the condition.

The second condition ensures that the prefix elements do not accidentally increase the count beyond n - i. Together, these conditions guarantee that exactly x elements are greater than or equal to x.

Python Solution

from typing import List

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

        for i in range(n):
            candidate = n - i

            if nums[i] >= candidate:
                if i == 0 or nums[i - 1] < candidate:
                    return candidate

        return -1

The implementation begins by sorting the array. Once sorted, every suffix of the array contains elements greater than or equal to the first value in that suffix.

The variable candidate represents the number of elements from the current index to the end of the array.

The first condition:

nums[i] >= candidate

checks whether all elements in the suffix are large enough.

The second condition:

i == 0 or nums[i - 1] < candidate

ensures that no earlier elements also qualify, which would increase the count beyond the candidate value.

If both conditions hold, we immediately return the candidate because the problem guarantees uniqueness.

If no valid candidate exists, the function returns -1.

Go Solution

package main

import "sort"

func specialArray(nums []int) int {
	sort.Ints(nums)

	n := len(nums)

	for i := 0; i < n; i++ {
		candidate := n - i

		if nums[i] >= candidate {
			if i == 0 || nums[i-1] < candidate {
				return candidate
			}
		}
	}

	return -1
}

The Go implementation follows the exact same logic as the Python solution.

The primary difference is that Go uses sort.Ints(nums) to sort the slice in place. Slices in Go already behave like references to underlying arrays, so no additional copying is required.

There are no integer overflow concerns because the constraints are extremely small.

Worked Examples

Example 1

Input: nums = [3,5]

After sorting:

[3,5]
i nums[i] candidate = n - i nums[i] >= candidate previous valid? Result
0 3 2 Yes i == 0 Return 2

The answer is 2.

Example 2

Input: nums = [0,0]

After sorting:

[0,0]
i nums[i] candidate nums[i] >= candidate Result
0 0 2 No Continue
1 0 1 No Continue

No valid candidate exists, so we return -1.

Example 3

Input: nums = [0,4,3,0,4]

After sorting:

[0,0,3,4,4]
i nums[i] candidate nums[i] >= candidate previous valid? Result
0 0 5 No - Continue
1 0 4 No - Continue
2 3 3 Yes 0 < 3 Return 3

The answer is 3.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(1) or O(log n) Depends on the sorting implementation

The algorithm spends most of its time sorting the array. After sorting, the linear scan is only O(n).

Python's sorting algorithm may use additional stack space internally, while Go's sort implementation also uses some recursion stack space. No extra data structures proportional to the input size are created.

Test Cases

from typing import List

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

        for i in range(n):
            candidate = n - i

            if nums[i] >= candidate:
                if i == 0 or nums[i - 1] < candidate:
                    return candidate

        return -1

sol = Solution()

assert sol.specialArray([3, 5]) == 2              # basic valid case
assert sol.specialArray([0, 0]) == -1             # all zeros
assert sol.specialArray([0, 4, 3, 0, 4]) == 3     # mixed values

assert sol.specialArray([1]) == 1                 # single element valid
assert sol.specialArray([0]) == -1                # single zero invalid

assert sol.specialArray([3, 6, 7, 7, 0]) == -1   # no valid x
assert sol.specialArray([4, 4, 4, 4]) == 4       # all elements satisfy
assert sol.specialArray([0, 1, 2, 3, 4]) == 2    # valid x not in array
assert sol.specialArray([100]) == 1               # very large value
assert sol.specialArray([0, 0, 3, 3]) == 2       # repeated large values
assert sol.specialArray([2, 2, 2]) == -1         # count mismatch
assert sol.specialArray([5, 5, 5, 5, 5]) == 5    # maximum possible x

Test Summary

Test Why
[3,5] Basic example with valid answer
[0,0] No valid x exists
[0,4,3,0,4] Mixed values with duplicates
[1] Smallest valid array
[0] Smallest invalid array
[3,6,7,7,0] No candidate satisfies condition
[4,4,4,4] Every element contributes
[0,1,2,3,4] Valid x does not appear in array
[100] Large number with small array
[0,0,3,3] Duplicate qualifying elements
[2,2,2] Candidate count mismatch
[5,5,5,5,5] x equals array length

Edge Cases

One important edge case is an array containing only zeros, such as [0,0]. A naive implementation might incorrectly think x = 0 works because no elements are greater than or equal to a positive number. However, when x = 0, every element is greater than or equal to 0, so the count becomes the full array length instead of zero. The implementation correctly handles this by explicitly checking the exact count condition.

Another important case is when the valid x does not appear in the array itself. For example, in [0,1,2,3,4], the answer is 2, even though 2 is only one of several values. The algorithm never assumes that x must exist in the array. Instead, it derives candidates from the number of remaining elements after sorting.

A third edge case involves duplicate values near the boundary. Consider [0,0,3,3]. Here, exactly two elements are greater than or equal to 2. The second condition:

nums[i - 1] < candidate

is essential because it prevents overcounting when repeated values appear. Without this check, the algorithm could incorrectly accept candidates where more than x elements satisfy the condition.

A final subtle case occurs when every element qualifies, such as [5,5,5,5,5]. In this situation, the valid answer is the array length itself. The implementation correctly handles this because the first index naturally represents a suffix containing the entire array.