Special Array With X Elements >= X Solution

The problem

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.

Python

def special_array(nums):
    nums.sort()
    for x in range(len(nums) + 1):
        count = sum(1 for num in nums if num >= x)
        if count == x:
            return x
    return -1

nums = [0, 4, 3, 0, 4]
print(special_array(nums))

Java

import java.util.Arrays;

public class SpecialArray {
    public int specialArray(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int x = 0; x <= n; x++) {
            int count = 0;
            for (int num : nums) {
                if (num >= x) {
                    count++;
                }
            }
            if (count == x) {
                return x;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        SpecialArray sa = new SpecialArray();
        int[] nums = {0, 4, 3, 0, 4};
        System.out.println(sa.specialArray(nums));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int specialArray(std::vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    int n = nums.size();
    for (int x = 0; x <= n; ++x) {
        int count = 0;
        for (auto num : nums) {
            if (num >= x) {
                count++;
            }
        }
        if (count == x) {
            return x;
        }
    }
    return -1;
}

int main() {
    std::vector<int> nums = {0, 4, 3, 0, 4};
    std::cout << specialArray(nums) << std::endl;
    return 0;
}

JavaScript

function specialArray(nums) {
    nums.sort((a, b) => a - b);
    for (let x = 0; x <= nums.length; x++) {
        let count = nums.filter(num => num >= x).length;
        if (count === x) {
            return x;
        }
    }
    return -1;
}

const nums = [0, 4, 3, 0, 4];
console.log(specialArray(nums));

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int specialArray(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), compare);
    for (int x = 0; x <= numsSize; x++) {
        int count = 0;
        for (int i = 0; i < numsSize; i++) {
            if (nums[i] >= x) {
                count++;
            }
        }
        if (count == x) {
            return x;
        }
    }
    return -1;
}

int main() {
    int nums[] = {0, 4, 3, 0, 4};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int result = specialArray(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

using System;
using System.Linq;

class SpecialArray {
    public int SpecialArrayFunc(int[] nums) {
        Array.Sort(nums);
        int n = nums.Length;
        for (int x = 0; x <= n; x++) {
            int count = nums.Count(num => num >= x);
            if (count == x) {
                return x;
            }
        }
        return -1;
    }

    static void Main() {
        SpecialArray sa = new SpecialArray();
        int[] nums = {0, 4, 3, 0, 4};
        Console.WriteLine(sa.SpecialArrayFunc(nums));
    }
}

This Python function sorts the number list, and for each possible x, verifies the count of elements greater than or equal to x, returning x if criteria match.

Complexity

Time Complexity: O(n log n) for sorting, followed by O(n) for counting, making it O(n log n) overall. Space Complexity: O(1) for additional storage.

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.

Python

def count_greater_equal(nums, target):
    return sum(1 for num in nums if num >= target)

def special_array(nums):
    nums.sort()
    left, right = 0, len(nums)
    while left <= right:
        mid = left + (right - left) // 2
        count = count_greater_equal(nums, mid)
        if count == mid:
            return mid
        elif count < mid:
            right = mid - 1
        else:
            left = mid + 1
    return -1

nums = [0, 4, 3, 0, 4]
print(special_array(nums))

Java

import java.util.Arrays;

public class SpecialArray {
    private static int countGreaterEqual(int[] nums, int target) {
        int count = 0;
        for (int num : nums) {
            if (num >= target) count++;
        }
        return count;
    }

    public int specialArray(int[] nums) {
        Arrays.sort(nums);
        int left = 0, right = nums.length;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int count = countGreaterEqual(nums, mid);
            if (count == mid) {
                return mid;
            } else if (count < mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        SpecialArray sa = new SpecialArray();
        int[] nums = {0, 4, 3, 0, 4};
        System.out.println(sa.specialArray(nums));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int countGreaterEqual(const std::vector<int>& nums, int target) {
    return std::count_if(nums.begin(), nums.end(), [target](int num) { return num >= target; });
}

int specialArray(std::vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    int n = nums.size();
    int left = 0, right = n;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int count = countGreaterEqual(nums, mid);
        if (count == mid) {
            return mid;
        } else if (count < mid) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

int main() {
    std::vector<int> nums = {0, 4, 3, 0, 4};
    std::cout << specialArray(nums) << std::endl;
    return 0;
}

JavaScript

function countGreaterEqual(nums, target) {
    return nums.filter(num => num >= target).length;
}

function specialArray(nums) {
    nums.sort((a, b) => a - b);
    let left = 0;
    let right = nums.length;
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        let count = countGreaterEqual(nums, mid);
        if (count === mid) {
            return mid;
        } else if (count < mid) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

const nums = [0, 4, 3, 0, 4];
console.log(specialArray(nums));

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int countGreaterEqual(int *nums, int numsSize, int target) {
    int count = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] >= target) {
            count++;
        }
    }
    return count;
}

int specialArray(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), compare);
    int left = 0, right = numsSize;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int count = countGreaterEqual(nums, numsSize, mid);
        if (count == mid) {
            return mid;
        } else if (count < mid) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

int main() {
    int nums[] = {0, 4, 3, 0, 4};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int result = specialArray(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

using System;
using System.Linq;

class SpecialArray {
    private int CountGreaterEqual(int[] nums, int target) {
        return nums.Count(num => num >= target);
    }

    public int SpecialArrayFunc(int[] nums) {
        Array.Sort(nums);
        int left = 0, right = nums.Length;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int count = CountGreaterEqual(nums, mid);
            if (count == mid) {
                return mid;
            } else if (count < mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    static void Main() {
        SpecialArray sa = new SpecialArray();
        int[] nums = {0, 4, 3, 0, 4};
        Console.WriteLine(sa.SpecialArrayFunc(nums));
    }
}

This Python approach leverages binary search to locate the special integer x efficiently, checking mid against counts.

Complexity

Time Complexity: O(n log n) including the sorting and binary search processes. Space Complexity: O(1) more storage requirement.

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

TypeScript

function specialArray(nums: number[]): number {
    const n = nums.length;
    for (let i = 0; i <= n; i++) {
        if (i === nums.reduce((r, v) => r + (v >= i ? 1 : 0), 0)) {
            return i;
        }
    }
    return -1;
}

func specialArray(nums []int) int {
	for x := 1; x <= len(nums); x++ {
		cnt := 0
		for _, v := range nums {
			if v >= x {
				cnt++
			}
		}
		if cnt == x {
			return x
		}
	}
	return -1
}

Rust

impl Solution {
    pub fn special_array(nums: Vec<i32>) -> i32 {
        let n = nums.len() as i32;
        for i in 0..=n {
            let mut count = 0;
            for &num in nums.iter() {
                if num >= i {
                    count += 1;
                }
            }
            if count == i {
                return i;
            }
        }
        -1
    }
}

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.

TypeScript

function specialArray(nums: number[]): number {
    const n = nums.length;
    let left = 0;
    let right = n + 1;
    while (left < right) {
        const mid = (left + right) >> 1;
        const count = nums.reduce((r, v) => r + (v >= mid ? 1 : 0), 0);

        if (count === mid) {
            return mid;
        }

        if (count > mid) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return -1;
}

func specialArray(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	for x := 1; x <= n; x++ {
		left, right := 0, n
		for left < right {
			mid := (left + right) >> 1
			if nums[mid] >= x {
				right = mid
			} else {
				left = mid + 1
			}
		}
		cnt := n - left
		if cnt == x {
			return x
		}
	}
	return -1
}

Rust

use std::cmp::Ordering;
impl Solution {
    pub fn special_array(nums: Vec<i32>) -> i32 {
        let n = nums.len() as i32;
        let mut left = 0;
        let mut right = n + 1;
        while left < right {
            let mid = left + (right - left) / 2;
            let mut count = 0;
            for &num in nums.iter() {
                if num >= mid {
                    count += 1;
                }
            }
            match count.cmp(&mid) {
                Ordering::Equal => {
                    return mid;
                }
                Ordering::Less => {
                    right = mid;
                }
                Ordering::Greater => {
                    left = mid + 1;
                }
            }
        }
        -1
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sorting and Linear Scan	Time Complexity: O(n log n) for sorting, followed by O(n) for counting, making it O(n log n) overall. Space Complexity: O(1) for additional storage.
Binary Search on Result	Time Complexity: O(n log n) including the sorting and binary search processes. Space Complexity: O(1) more storage requirement.
Brute Force Enumeration	–
Sorting + Binary Search	–

Complexity analysis

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

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.

Special Array With X Elements Greater Than or Equal X solution and explanation

The problem

Approach overview

Approach 1: Sorting and Linear Scan

Approach 2: Binary Search on Result

Approach 3: Brute Force Enumeration

Approach 4: Sorting + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Special Array With X Elements Greater Than or Equal X solution and explanation

The problem

Approach overview

Approach 1: Sorting and Linear Scan

Approach 2: Binary Search on Result

Approach 3: Brute Force Enumeration

Approach 4: Sorting + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems