Skip to main content
Talentd

Count Elements With at Least K Greater Values - Solution & Explanation

MediumArrayBinary SearchDivide and ConquerSorting7 min read
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 109
  • 0 <= k < n

Approach Overview

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

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair ComparisonO(n²)O(1)Small arrays or when validating logic before optimization
Sorting + Threshold CheckO(n log n)O(1)–O(n)General case; simplest and most reliable implementation
Quickselect (k-th Largest)O(n) average, O(n²) worstO(1)When you want linear average time without sorting the entire array

Video Solution

Count Elements With at Least K Greater Values | Weekly Contest 478 | Java| Developer Coder • Developer Coder • 507 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Elements With at Least K Greater Values easy or hard?
The problem is generally considered medium difficulty. The logic becomes straightforward once you recognize that the k-th largest element defines a threshold. The challenge lies in translating the "k greater elements" condition into a ranking or selection problem.
Count Elements With at Least K Greater Values Python/Java solution
In Python or Java, the typical solution sorts the array and identifies the k-th largest value using index n - k. Then iterate through the array and count elements strictly smaller than this threshold. The implementation is short and runs in O(n log n) time with constant or linear auxiliary space depending on the sorting implementation.
How to solve Count Elements With at Least K Greater Values in O(n)?
Use Quickselect to find the k-th largest element in the array without fully sorting it. This value becomes the threshold such that any element strictly smaller than it has at least k greater elements. After finding the threshold, perform one linear pass to count qualifying elements, giving O(n) average time complexity.
What is the best approach for Count Elements With at Least K Greater Values?
The most practical approach is sorting the array and identifying the k-th largest value as a threshold. After sorting, any element strictly smaller than nums[n - k] has at least k greater values. This solution runs in O(n log n) time and uses minimal extra space, making it easy to implement and reliable in interviews.
Is Count Elements With at Least K Greater Values asked at Google/Amazon/Meta?
Problems involving order statistics, k-th largest elements, and array ranking frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often test sorting, heap usage, or Quickselect. This problem specifically checks whether you can translate a ranking condition into a threshold-based solution.
What data structure is used in Count Elements With at Least K Greater Values?
The core structure is a simple array. Algorithms commonly applied include sorting or selection algorithms like Quickselect. Some variations may also use heaps or binary search over sorted arrays to determine how many elements are greater than a given value.
What is the time complexity of Count Elements With at Least K Greater Values?
The common sorting solution runs in O(n log n) time due to the sorting step, followed by a linear scan. A brute force approach takes O(n²) time because each element compares against all others. Using Quickselect to find the k-th largest element reduces the average complexity to O(n).

Ready to solve this problem?

Practice Count Elements With at Least K Greater Values with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays