You are given an integer array nums of length n and an integer k.
An element in nums is said to be qualified if there exist at least k elements in the array that are strictly greater than it.
Return an integer denoting the total number of qualified elements in nums.
Example 1:
Input: nums = [3,1,2], k = 1
Output: 2
Explanation:
The elements 1 and 2 each have at least k = 1 element greater than themselves.
No element is greater than 3. Therefore, the answer is 2.
Example 2:
Input: nums = [5,5,5], k = 2
Output: 0
Explanation:
Since all elements are equal to 5, no element is greater than the other. Therefore, the answer is 0.
Constraints:
1 <= n == nums.length <= 1051 <= nums[i] <= 1090 <= k < nProblem Overview: Given an integer array, count how many elements have at least k strictly greater values somewhere else in the array. For each element x, you check how many numbers in the array are greater than x. If that count is >= k, the element contributes to the answer.
Approach 1: Brute Force (O(n²) time, O(1) space)
Check every pair of elements. For each index i, iterate through the entire array and count how many values are strictly greater than nums[i]. If the count reaches k, increment the result. This approach uses simple nested iteration over the array. It is easy to reason about and useful for validating logic, but it becomes slow when n grows because every element triggers another full scan.
Approach 2: Sorting (O(n log n) time, O(1) or O(n) space)
Sort the array in ascending order using a standard sorting algorithm. After sorting, the k-th largest value sits at index n - k. Any element strictly smaller than this value must have at least k greater elements to its right in the sorted order. Iterate through the array and count numbers < nums[n - k]. Duplicates of the threshold value are excluded because they do not have enough strictly greater elements. This method is straightforward and reliable, making it a common production solution.
Approach 3: Quickselect / Selection (O(n) average time, O(1) space)
Instead of fully sorting the array, you can locate the k-th largest element using Quickselect, a selection algorithm related to divide and conquer. Partition the array repeatedly until the element at position n - k is placed correctly. This value acts as the threshold. Once found, perform a single pass and count elements strictly smaller than it. Quickselect reduces unnecessary ordering work and improves average performance to linear time, though the worst case is still O(n²) if partitioning is poor.
Recommended for interviews: Start by explaining the brute force solution to show you understand the requirement. Then move to the sorting approach, which is clean and easy to implement under pressure with O(n log n) time. If the interviewer asks for further optimization, mention Quickselect to achieve O(n) average time by finding the k-th largest value without fully sorting the array.
If k = 0, then all elements in the array are qualified elements, and we can directly return the length of the array.
Otherwise, we sort the array, and let n be the length of the sorted array. For each index i satisfying 0 leq i < n - k, if the element at index i is strictly less than the element at index n - k, then it is a qualified element. We just need to count the number of such elements and return it.
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 nums.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n²) | O(1) | Small arrays or when validating logic before optimization |
| Sorting + Threshold Check | O(n log n) | O(1)–O(n) | General case; simplest and most reliable implementation |
| Quickselect (k-th Largest) | O(n) average, O(n²) worst | O(1) | When you want linear average time without sorting the entire array |
Count Elements With at Least K Greater Values | Weekly Contest 478 | Java| Developer Coder • Developer Coder • 495 views views
Watch 9 more video solutions →Practice Count Elements With at Least K Greater Values with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor