Watch 10 video solutions for Count Elements With at Least K Greater Values, a medium level problem involving Array, Binary Search, Divide and Conquer. This walkthrough by Developer Coder has 495 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |