Special Array With X Elements Greater Than or Equal X

Easy
264.

Special Array With X Elements Greater Than or Equal X

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.

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 <= 40
  • 0 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var specialArray = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 40
  • 0 <= nums[i] <= 1000

Hints for Special Array With X Elements Greater Than or Equal X

  1. Hint 1

    x can never exceed the array's length, so only 0 … n are worth testing.

  2. Hint 2

    For each candidate, count how many elements clear the bar and check for equality.

  3. 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

  1. For x from 0 to n, count elements >= x.
  2. Return the first x whose count equals x; 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

  • x need 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 -1

Java

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