Special Array With X Elements Greater Than or Equal X Solution
Special Array With X Elements Greater Than or Equal X solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Special Array With X Elements Greater Than or Equal X is an easy coding problem on arrays, sorting and binary search, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting, Binary Search, Counting Sort
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An array nums is special if there exists a number x such that exactly x elements of nums are greater than or equal to x. Note that x itself need not be an element of nums.
Return that x if the array is special, otherwise return -1. It can be proved that at most one such x exists.
Example 1
Input: nums = [3,5]
Output: 2
Explanation: Two elements are at least 2.
Example 2
Input: nums = [0,0]
Output: -1
Example 3
Input: nums = [0,4,3,0,4]
Output: 3
Explanation: Three elements are at least 3.
Constraints
1 <= nums.length <= 400 <= nums[i] <= 1000
Hints for Special Array With X Elements Greater Than or Equal X
Hint 1
xcan never exceed the array's length, so only0 … nare worth testing.Hint 2
For each candidate, count how many elements clear the bar and check for equality.
Hint 3
Sorting first turns the count into a binary search, giving O(n log n).
How to solve Special Array With X Elements Greater Than or Equal X
x cannot exceed n, so test every x in 0..n by counting how many elements are at least x.
Approach
- For
xfrom 0 ton, count elements>= x. - Return the first
xwhose count equalsx; else-1.
Why it works
The count of elements >= x is non-increasing in x while x itself increases, so they cross at most once — which is why the answer is unique and a linear scan (or a binary search over sorted input) finds it.
Complexity
- Time —
O(n²), or O(n log n) with a sort and binary search - Space —
O(1)
Pitfalls
xneed not be an element of the array.
Reference solution
Python
def specialArray(nums) -> int:
for x in range(len(nums) + 1):
if sum(1 for v in nums if v >= x) == x:
return x
return -1Java
public static int specialArray(int[] nums) {
for (int x = 0; x <= nums.length; x++) {
int count = 0;
for (int v : nums) {
if (v >= x) count++;
}
if (count == x) return x;
}
return -1;
}C++
int specialArray(vector<int>& nums) {
for (int x = 0; x <= (int) nums.size(); x++) {
int count = 0;
for (int v : nums) {
if (v >= x) count++;
}
if (count == x) return x;
}
return -1;
}JavaScript
var specialArray = function(nums) {
for (let x = 0; x <= nums.length; x++) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] >= x) count++;
}
if (count === x) return x;
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms