3759. Count Elements With at Least K Greater Values

MediumArrayBinary SearchDivide and ConquerQuickselectSorting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

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.

In other words, for an element x in nums, count how many other elements are strictly greater than x. If that count is at least k, then x is qualified.

Return an integer denoting the total number of qualified elements in nums.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Binary Search?

This problem maps to Binary Search through a short path in the full flowchart.

Sorting the array and then counting elements strictly smaller than the element at the kth-from-end position uses the sorted order for efficient counting.

Open in Flowchart

Intuition

The key observation is that whether an element is qualified depends only on how many elements are strictly greater than it. Counting "greater than" relationships becomes much easier once the array is sorted.

First, consider the special case when k = 0. Since every element needs at least 0 elements greater than it, this condition is always satisfied. So all n elements are qualified, and we can directly return n.

For the general case, let's think about what happens after we sort the array in ascending order. In a sorted array of length n, the element at index n - k is exactly the element such that there are k elements positioned after it (at indices n - k + 1, n - k + 2, ..., n - 1). These trailing k elements are all greater than or equal to it.

Now, for any element at index i where 0 <= i < n - k, if its value is strictly less than the value at index n - k, then the value at n - k along with all k - 1 elements after it (which are at least as large) gives us at least k elements strictly greater than nums[i]. This means nums[i] is qualified.

On the other hand, elements at indices i >= n - k cannot possibly have k elements strictly greater than them, because there simply aren't enough larger elements remaining to their right. So we only need to check indices in the range 0 <= i < n - k.

This leads us to a clean approach: sort the array, then count how many elements among the first n - k positions are strictly smaller than nums[n - k].

Pattern Learn more about Binary Search, Divide and Conquer and Sorting patterns.

Solution Approach

Solution 1: Sorting

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

Let's break down the implementation step by step:

Handle the edge case: Compute n = len(nums). If k == 0, return n immediately, since every element trivially satisfies the condition.
Sort the array: Call nums.sort() to arrange the elements in ascending order. After sorting, the relative ordering allows us to use a single reference point.
Pick the reference element: The element at index n - k serves as the threshold. Any element strictly smaller than nums[n - k] has at least k elements greater than it (the element at n - k plus the k - 1 elements after it).
Count qualified elements: Iterate over indices i from 0 to n - k - 1, and count how many satisfy nums[n - k] > nums[i]. This is done concisely with sum(nums[n - k] > nums[i] for i in range(n - k)), where each True contributes 1 to the sum.

The time complexity is O(n log n), dominated by the sorting step, where n is the length of the array. The space complexity is O(log n), accounting for the stack space used during sorting.

Example Walkthrough

Let's trace through the solution approach with a small concrete example.

Input: nums = [3, 1, 4, 2, 5], k = 2

We want to count how many elements have at least 2 elements strictly greater than them.

Step 1: Handle the edge case

Compute n = len(nums) = 5. Since k = 2 is not 0, we skip the early return and proceed.

Step 2: Sort the array

After calling nums.sort(), the array becomes:

Index:   0    1    2    3    4
Value:   1    2    3    4    5

Step 3: Pick the reference element

The threshold is at index n - k = 5 - 2 = 3, so the reference value is nums[3] = 4.

The reasoning: any element strictly smaller than nums[3] = 4 is guaranteed to have at least k = 2 elements greater than it — namely nums[3] = 4 itself plus the k - 1 = 1 element after it (nums[4] = 5).

Step 4: Count qualified elements

We only iterate over indices i from 0 to n - k - 1 = 2, comparing each against the threshold nums[3] = 4:

Index `i`	`nums[i]`	`nums[3] > nums[i]`?	Qualified?
0	1	`4 > 1` → True	✅ Yes
1	2	`4 > 2` → True	✅ Yes
2	3	`4 > 3` → True	✅ Yes

Indices 3 and 4 are skipped entirely, since elements at positions i >= n - k cannot possibly have 2 larger elements remaining to their right.

Summing the True values gives 1 + 1 + 1 = 3.

Verification

Let's confirm by checking each original element directly:

1: greater elements are {2, 3, 4, 5} → 4 ≥ 2 ✅
2: greater elements are {3, 4, 5} → 3 ≥ 2 ✅
3: greater elements are {4, 5} → 2 ≥ 2 ✅
4: greater elements are {5} → 1 < 2 ❌
5: greater elements are {} → 0 < 2 ❌

The count is 3, matching our result.

Output: 3

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def countElements(self, nums: List[int], k: int) -> int:
6        # Total number of elements in the list
7        length = len(nums)
8
9        # When k is 0, the original code returns the full length
10        if k == 0:
11            return length
12
13        # Sort the list in ascending order so positions have meaning
14        nums.sort()
15
16        # Use nums[length - k] as the pivot (the k-th element from the end).
17        # Count how many of the first (length - k) elements are strictly
18        # smaller than this pivot value.
19        pivot = nums[length - k]
20        return sum(pivot > nums[i] for i in range(length - k))
21```
22
23**A note on the algorithm:**
24
25The standard LeetCode problem **"Count Elements With Strictly Smaller and Greater Elements"** asks you to count elements that have at least one element strictly smaller *and* at least one strictly greater. The clean solution for that is:
26
27```python3
28from typing import List
29
30
31class Solution:
32    def countElements(self, nums: List[int]) -> int:
33        # An element counts only if it is strictly greater than the minimum
34        # and strictly less than the maximum.
35        smallest = min(nums)
36        largest = max(nums)
37        return sum(smallest < num < largest for num in nums)
38

1class Solution {
2    public int countElements(int[] nums, int k) {
3        // Total number of elements in the array
4        int length = nums.length;
5
6        // When k is 0, no elements are excluded from the top,
7        // so every element satisfies the condition
8        if (k == 0) {
9            return length;
10        }
11
12        // Sort the array in ascending order so we can locate
13        // the boundary value at position (length - k)
14        Arrays.sort(nums);
15
16        // Counter for elements strictly less than the boundary value
17        int count = 0;
18
19        // The element at index (length - k) marks where the top k largest values begin.
20        // We only need to scan the elements before this position.
21        int boundaryValue = nums[length - k];
22
23        // Count how many elements are strictly smaller than the boundary value
24        for (int i = 0; i < length - k; ++i) {
25            if (boundaryValue > nums[i]) {
26                ++count;
27            }
28        }
29
30        return count;
31    }
32}
33

1class Solution {
2public:
3    int countElements(vector<int>& nums, int k) {
4        int n = nums.size();
5
6        // If k is 0, every element is trivially counted.
7        if (k == 0) {
8            return n;
9        }
10
11        // Sort the array in ascending order so we can locate
12        // the boundary element by its index easily.
13        ranges::sort(nums);
14
15        int ans = 0;
16
17        // After sorting, nums[n - k] is the element such that there are
18        // exactly k elements greater than or equal to it from the top.
19        // We count how many elements are strictly smaller than nums[n - k];
20        // each of these has at least k elements greater than it and at
21        // least one element smaller, satisfying the counting condition.
22        int boundary = nums[n - k];
23        for (int i = 0; i < n - k; ++i) {
24            if (boundary > nums[i]) {
25                ++ans;
26            }
27        }
28
29        return ans;
30    }
31};
32

1/**
2 * Counts how many elements remain "valid" after conceptually removing the k
3 * largest elements: an element is counted if it is strictly smaller than the
4 * smallest of the removed (top-k) values.
5 *
6 * @param nums - The input array of numbers.
7 * @param k    - The number of largest elements to set aside.
8 * @returns The count of elements strictly less than the k-th largest value.
9 */
10function countElements(nums: number[], k: number): number {
11    // Total number of elements in the array.
12    const length: number = nums.length;
13
14    // When k is 0, no elements are removed, so every element is counted.
15    if (k === 0) {
16        return length;
17    }
18
19    // Sort the array in ascending order so we can locate the boundary easily.
20    nums.sort((a: number, b: number): number => a - b);
21
22    // Accumulator for the number of qualifying elements.
23    let answer: number = 0;
24
25    // The element at index (length - k) is the smallest among the top-k values
26    // after sorting. We only iterate over elements before this boundary.
27    const boundaryValue: number = nums[length - k];
28
29    // Count every element strictly less than the boundary value.
30    for (let i: number = 0; i < length - k; ++i) {
31        if (boundaryValue > nums[i]) {
32            ++answer;
33        }
34    }
35
36    return answer;
37}
38

Time and Space Complexity

Time Complexity: O(n × log n)

The analysis is broken down by the main operations in the code:

Length and early return check: Computing len(nums) and checking k == 0 both take O(1) time.
Sorting: The call nums.sort() dominates the runtime. Python's built-in sort (Timsort) has a time complexity of O(n × log n), where n is the length of nums.
Summation loop: The expression sum(nums[n - k] > nums[i] for i in range(n - k)) iterates over at most n - k elements, each comparison being O(1). This contributes O(n) time.

Combining these, the total time complexity is O(n × log n) + O(n) = O(n × log n).

Space Complexity: O(log n)

The space analysis focuses on the extra memory used:

Sorting: Python's Timsort requires O(log n) auxiliary space for its recursion/merge stack in the typical case.
Summation generator: The sum over a generator expression uses only O(1) additional space, since values are produced and consumed one at a time without building an intermediate list.

Therefore, the dominant extra space usage comes from the sort, giving an overall space complexity of O(log n), where n is the length of the array nums.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misidentifying the Threshold Index as `n - k - 1` Instead of `n - k`

The most frequent mistake is confusing which sorted position serves as the correct reference point. A natural but incorrect intuition is: "If I want at least k elements strictly greater than x, I should look at the element at index n - k - 1, because that's where the last k elements begin."

This off-by-one error breaks the counting logic. Let's reason through it carefully.

After sorting in ascending order, the k largest elements occupy indices n - k, n - k + 1, ..., n - 1. For an element at index i to have at least k elements strictly greater than it, every one of those k trailing elements must be strictly greater than nums[i]. Since the array is sorted, the smallest of those k trailing elements is nums[n - k]. Therefore, the condition simplifies to:

nums[n - k] > nums[i]

If this holds, then all k elements from index n - k onward are strictly greater (they are all >= nums[n - k] > nums[i]).

Incorrect version:

pivot = nums[length - k - 1]  # WRONG: this only guarantees k-1 greater elements
return sum(pivot > nums[i] for i in range(length - k - 1))

Using index n - k - 1 would only guarantee k - 1 strictly greater elements above it, undercounting the threshold and producing wrong answers (and risking an out-of-range index when k == n).

Correct version:

pivot = nums[length - k]
return sum(pivot > nums[i] for i in range(length - k))

Pitfall 2: Forgetting the `k == 0` Edge Case

When k == 0, every element qualifies because the condition "at least 0 elements are strictly greater" is trivially satisfied for all elements. However, if you skip the early return and compute length - k, you get nums[length - 0] = nums[length], which is an index-out-of-bounds access.

# Without the guard, this crashes when k == 0:
pivot = nums[length - k]  # nums[length] -> IndexError

Always handle k == 0 explicitly by returning length before touching the pivot:

if k == 0:
    return length

Pitfall 3: Assuming `k <= n` Without Validation

If k can exceed n (depending on the problem constraints), then no element can possibly have k strictly greater elements, so the answer must be 0. The current code assumes 0 <= k <= n. If your input may violate this, guard against it:

if k > length:
    return 0

When the constraints guarantee k <= n, this check is unnecessary, but it's worth confirming the bounds before relying on nums[length - k] being a valid index.

Pitfall 4: Using `>=` Instead of `>` (Strictly Greater)

The problem requires elements that are strictly greater. Counting with nums[n - k] >= nums[i] instead of nums[n - k] > nums[i] would incorrectly include elements equal to the pivot.

Consider nums = [2, 2, 2, 2] with k = 2. After sorting, pivot = nums[2] = 2. No element is strictly less than 2, so the answer is 0. Using >= would wrongly count all the equal elements, inflating the result. Always preserve the strict comparison to match the "strictly greater than" requirement.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering