Abstract / Summary

Given an array, find the largest number x such that there are at least x elements in the array that are greater than or equal to x.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 67% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a method specialArray that determines a special integer x for a given list of integers nums. The special integer is defined such that exactly x elements in the array are greater than or equal to x. The algorithm proceeds by sorting the input, then iteratively examining possible values of x while maintaining a running reference to previously removed elements. If a suitable x is found, it is returned; otherwise the method returns -1.

Sorting the Input

The first operational step is a call to the built-in sort method on the list.

nums.sort()

Sorting arranges the numbers in non-decreasing order, which enables the subsequent logic to treat the smallest remaining element as an upper bound for the current candidate x. By ordering the data, the algorithm can make deterministic comparisons without scanning the entire list for each candidate.

Iterative Search Loop

The core of the algorithm is a while loop that continues until the list becomes empty.

prev = -inf
while nums:
    x = len(nums)
    if prev < x <= nums[0]:
        return x
    prev = heappop(nums)

Inside the loop, x is set to the current length of nums, representing the number of elements that would be considered “greater than or equal to x” if the current slice were the whole array. The conditional prev < x <= nums[0] checks two constraints: x must be larger than any value previously removed (prev) and must not exceed the smallest element still present (nums[0]). When both conditions hold, x satisfies the definition of a special integer and is returned immediately.

If the condition fails, the smallest element is removed from the list using heappop. Although nums is a plain list, the use of heappop treats it as a min-heap, extracting the minimal value in logarithmic time. The extracted value is stored in prev for the next iteration’s comparison.

When the loop exhausts all elements without finding a valid x, the method concludes that no special integer exists and returns -1.

Edge Cases Handled

The algorithm gracefully handles the scenario where the input list is empty. Since nums.sort() on an empty list is a no-op, the subsequent while nums: condition fails immediately, leading to the final return -1. This correctly indicates the absence of a special integer.

Another edge case involves arrays where all elements are identical. After sorting, the smallest element equals every other element, and the condition prev < x <= nums[0] will succeed precisely when the count of remaining elements matches that common value, yielding the correct special integer.

The use of prev initialized to negative infinity ensures that the first comparison does not inadvertently reject a valid candidate due to an uninitialized lower bound. This design accommodates the smallest possible candidate x = 1 without special casing.

Performance Optimizations

Sorting the list once at the beginning provides a deterministic order that eliminates the need for repeated scans of the array. By leveraging the sorted order, the algorithm reduces the problem to a single linear pass over the elements.

The choice of heappop for removing the smallest element introduces a heap-based extraction that operates in logarithmic time rather than linear time that a plain pop(0) would incur. This optimization is significant when the input size is large, as it keeps the overall runtime closer to O(n log n) dominated by the initial sort, while the iterative removals contribute only O(n log n) in total.

Storing the candidate length x as len(nums) avoids recomputing the count of remaining elements through explicit iteration, providing constant-time access to the current candidate value.

By returning as soon as a valid x is identified, the method avoids unnecessary further processing, ensuring that the best-case execution path terminates early when the special integer is found near the beginning of the loop.

Imagine you have a big pile of numbered building blocks. The computer starts by sorting these blocks from the smallest number to the largest number.

The code picks up a block from the pile one by one and looks at how many blocks are left in the pile. If the number of blocks remaining is a special magic number that fits perfectly between the size of the pile and what is written on the smallest block, the code gets excited and shouts that it found the answer.

If that magic fits, the computer stops looking. If it does not find that perfect fit, it removes the smallest block from the pile and keeps counting how many are left. It does this over and over again until either the special number is found or there are no more blocks left to check. If the pile disappears and no magic number appeared, the code says it could not find anything.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java						TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java			Go		Rust	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim								C
	everthis			JS
	fartem						Ruby
	fsq	C++
	halfrost							Go
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	shreymehul					C#
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality