Skip to main content
Talentd

Special Array With X Elements Greater Than or Equal X - Solution & Explanation

EasyArrayBinary SearchSorting17 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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.

 

Constraints:

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

Approach Overview

Problem Overview: You receive an integer array nums. The goal is to find a number x such that exactly x elements in the array are greater than or equal to x. If such a value exists, return it. Otherwise return -1. The value of x must be consistent with the count of elements meeting the condition.

Approach 1: Sorting and Linear Scan (Time: O(n log n), Space: O(1) or O(n) depending on sort)

Sort the array in non-decreasing order using a standard sorting algorithm. After sorting, iterate through the array and treat each position as a potential boundary where x elements remain on the right. If the array has n elements and you are at index i, then there are n - i elements that are >= nums[i]. Check whether n - i could be the special value by verifying that nums[i] >= n - i and the previous element (if it exists) is < n - i. The first position that satisfies this condition gives the correct x. Sorting groups smaller values on the left and larger ones on the right, which makes counting elements greater than or equal to a candidate value straightforward.

Approach 2: Binary Search on Result (Time: O(n log n), Space: O(1))

The possible value of x ranges from 0 to n. Instead of testing all values linearly, apply binary search on this range. For each candidate x, iterate through the array and count how many elements are >= x. If the count equals x, you found the special value. If the count is larger than x, move the search range higher; if smaller, move it lower. The binary search reduces the number of candidate checks while the counting step validates the condition. This technique is known as binary search on the answer, a common pattern for problems where the result lies within a numeric range.

Both approaches operate directly on the array and rely on counting elements that satisfy a threshold condition. The sorting approach leverages order to compute counts quickly from indices, while the binary search approach repeatedly evaluates candidate answers.

Recommended for interviews: The sorting and linear scan solution is usually the expected answer. It is simple, deterministic, and easy to reason about after ordering the array. Binary search on the result demonstrates stronger algorithmic thinking and familiarity with the "search on answer" pattern, but the sorting approach is typically faster to implement during interviews while still achieving optimal practical performance.

Approach 1: Sorting and Linear Scan

Sort the array first. For each possible count of elements x, check if there are exactly x numbers in the array that are greater than or equal to x.

This C program sorts the input array and then iterates to determine if the number of elements greater than or equal to x is exactly x.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting, followed by O(n) for checking, resulting in O(n log n). Space Complexity: O(1) additional space.

Try this approach in the editor →

Approach 2: Binary Search on Result

Utilize binary search on the result potential values from 0 to nums.length to efficiently find the special x.

This solution uses binary search over the number of potential special cases, reducing the search space for efficiency.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting initially, and O(n log n) for the binary search with counting operations. Space Complexity: O(1) additional space.

Try this approach in the editor →

Approach 3: Brute Force Enumeration

We enumerate x in the range of [1..n], and then count the number of elements in the array that are greater than or equal to x, denoted as cnt. If there exists cnt equal to x, return x directly.

The time complexity is O(n^2), where n is the length of the array. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 4: Sorting + Binary Search

We can also sort nums first.

Next, we still enumerate x, and use binary search to find the first element in nums that is greater than or equal to x, quickly counting the number of elements in nums that are greater than or equal to x.

The time complexity is O(n times log n), and the space complexity is O(log n). Where n is the length of the array.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting and Linear Scan

Time Complexity: O(n log n) due to sorting, followed by O(n) for checking, resulting in O(n log n). Space Complexity: O(1) additional space.

Binary Search on Result

Time Complexity: O(n log n) due to sorting initially, and O(n log n) for the binary search with counting operations. Space Complexity: O(1) additional space.

Brute Force Enumeration—
Sorting + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and Linear ScanO(n log n)O(1) or O(n)Best general solution; easy to reason about once the array is sorted
Binary Search on ResultO(n log n)O(1)Useful when practicing binary search on answer or when the valid result lies within a bounded numeric range

Video Solution

Special Array with X Elements Greater than or Equal X - Leetcode 1608 - Python • NeetCodeIO • 13,902 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Special Array With X Elements Greater Than or Equal X easy or hard?
This problem is classified as Easy on LeetCode. The main challenge is recognizing that the candidate value x represents a count of elements meeting a threshold condition. Once the array is sorted, verifying the condition becomes a straightforward linear scan.
Special Array With X Elements Greater Than or Equal X Python/Java solution
In Python or Java, the common implementation sorts the array using built-in functions such as sort() or Arrays.sort(). After sorting, iterate through the indices and compute n - i to represent how many elements remain that could be >= x. Check whether the boundary condition satisfies the definition of the special value.
How to solve Special Array With X Elements Greater Than or Equal X in O(n)?
A near O(n) approach can be achieved using counting or bucket frequency if the value range is limited to the array size. Count how many numbers fall into each bucket up to n, then compute suffix counts to determine how many values are >= each candidate x. Once the suffix count equals x, that value is the answer.
What is the best approach for Special Array With X Elements Greater Than or Equal X?
The most practical approach sorts the array and performs a linear scan to check how many elements remain at each position. After sorting, if there are n elements and you are at index i, then n - i elements are >= nums[i]. When nums[i] >= n - i and the previous value is smaller than n - i, that value becomes the special number x. This solution runs in O(n log n) time due to sorting.
Is Special Array With X Elements Greater Than or Equal X asked at Google/Amazon/Meta?
Problems involving threshold counts and binary search on the answer appear frequently in interviews at large companies like Google, Amazon, and Meta. While this exact problem may not always appear verbatim, the underlying patterns—sorting, counting elements >= a value, and binary search on a numeric range—are common interview topics.
What data structure is used in Special Array With X Elements Greater Than or Equal X?
The core data structure is a simple array. The algorithm relies on sorting the array and computing counts of elements greater than or equal to a threshold. Some variations use frequency arrays or prefix/suffix counts to speed up counting operations.
What is the time complexity of Special Array With X Elements Greater Than or Equal X?
The typical solution runs in O(n log n) time because the array is sorted first. After sorting, a single linear pass determines whether a valid x exists, which takes O(n). Space complexity is O(1) if the sorting algorithm is in-place, otherwise O(n) depending on the implementation.

Ready to solve this problem?

Practice Special Array With X Elements Greater Than or Equal X with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays