LeetCode 3759 - Count Elements With at Least K Greater Values

LeetCode Problem 3759

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Divide and Conquer, Sorting, Quickselect

Solution

Problem Understanding

The problem asks us to count how many elements in an array have at least k values that are strictly greater than them.

More concretely, for every element nums[i], we need to determine how many numbers in the array are larger than nums[i]. If that count is at least k, then the element is considered qualified. The final answer is the total number of qualified elements.

It is important to notice that the comparison is strictly greater, not greater than or equal to. This distinction matters when duplicate values exist. For example, if the array is [5, 5, 5], then no element has any strictly greater value, even though many elements are equal.

The input consists of:

• nums, an integer array of length n
• k, an integer threshold

The output is a single integer representing the number of qualified elements.

The constraints are significant:

• 1 <= n <= 10^5
• 1 <= nums[i] <= 10^9
• 0 <= k < n

Since n can be as large as 100,000, an algorithm with quadratic time complexity, O(n²), will likely be too slow. This immediately suggests we should look for a more efficient approach, typically involving sorting, binary search, or selection techniques.

Several edge cases stand out immediately:

• When k = 0, every element is automatically qualified because every element has at least zero greater elements.
• When all values are identical, no element can have a strictly greater value.
• Arrays with many duplicates can be tricky because equal elements do not count as greater.
• Large arrays require an efficient solution that avoids nested comparisons.

Approaches

Brute Force Approach

The most direct approach is to examine every element and count how many values in the array are strictly greater than it.

For each nums[i], we iterate through the entire array again and count how many nums[j] > nums[i]. If the count reaches at least k, we increment the answer.

This works because it explicitly checks the problem definition for every element. Since we test every possible comparison, the result is guaranteed to be correct.

However, this method is inefficient. For every one of the n elements, we potentially scan all n elements again. This leads to O(n²) time complexity, which becomes too slow when n = 100,000.

Optimal Approach, Sorting + Binary Search

The key observation is that we do not actually need to repeatedly count larger elements manually.

If we sort the array, the position of an element immediately tells us how many elements are greater than it.

Suppose the sorted array is:

[1, 2, 2, 4, 5]

For any value x, if we can find the first index where a number becomes strictly greater than x, then everything after that index is greater than x.

For example:

• For x = 2, the first greater element is 4 at index 3
• Total greater elements = 5 - 3 = 2

We can efficiently find this position using binary search.

The process becomes:

1. Sort the array.
2. For every original element:

• Use binary search to locate the first number greater than it.
• Compute how many numbers lie to the right.
• Check whether that count is at least k.

Binary search makes each lookup O(log n), and sorting costs O(n log n). The total complexity becomes O(n log n).

Although the topic list mentions Quickselect, sorting is the cleaner and more practical solution here. Quickselect can identify threshold values in expected linear time, but handling duplicates correctly becomes more complicated, while sorting provides a straightforward and reliable implementation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Compare every element with every other element
Optimal	O(n log n)	O(n)	Sort array and use binary search to count greater elements

Algorithm Walkthrough

Optimal Algorithm, Sorting + Binary Search

1. Create a sorted copy of the array.

We sort the numbers so that greater elements become grouped toward the end. This allows us to use binary search efficiently. 2. Initialize a counter for qualified elements.

We will increment this whenever an element satisfies the condition of having at least k greater values. 3. Iterate through every element in the original array.

We process elements in their original form because the answer concerns every occurrence, including duplicates. 4. Use binary search to find the first strictly greater value.

We search for the insertion point immediately after the current value. In Python, bisect_right() does exactly this. In Go, we can implement equivalent logic with sort.Search(). 5. Compute how many greater elements exist.

If the first greater element is found at index idx in the sorted array, then:

greater_count = n - idx

since all remaining elements are larger. 6. Check whether the count is at least k.

If greater_count >= k, increment the result. 7. Return the final count.

Why it works

The correctness comes from the sorted ordering of the array. After sorting, all elements strictly greater than a value x must appear consecutively after the last occurrence of x. Binary search finds the first such position efficiently. Since the number of greater elements is exactly the number of positions remaining in the sorted array, every element is classified correctly according to the problem definition.

Python Solution

from bisect import bisect_right
from typing import List

class Solution:
    def countElements(self, nums: List[int], k: int) -> int:
        sorted_nums = sorted(nums)
        n = len(nums)

        qualified_count = 0

        for value in nums:
            first_greater_index = bisect_right(sorted_nums, value)
            greater_count = n - first_greater_index

            if greater_count >= k:
                qualified_count += 1

        return qualified_count

The implementation starts by creating a sorted version of the input array. This preprocessing step enables efficient binary search operations.

For each value in nums, we use bisect_right() to locate the position immediately after the last occurrence of that value. This is important because the problem requires strictly greater values, meaning equal elements should not be counted.

Once we know the first position of a strictly greater value, the number of greater elements is simply the number of remaining values in the sorted array.

Finally, if the count meets or exceeds k, we increase the answer.

Go Solution

package main

import "sort"

func countElements(nums []int, k int) int {
	sortedNums := make([]int, len(nums))
	copy(sortedNums, nums)

	sort.Ints(sortedNums)

	n := len(nums)
	qualifiedCount := 0

	for _, value := range nums {
		firstGreaterIndex := sort.Search(
			n,
			func(i int) bool {
				return sortedNums[i] > value
			},
		)

		greaterCount := n - firstGreaterIndex

		if greaterCount >= k {
			qualifiedCount++
		}
	}

	return qualifiedCount
}

The Go implementation follows the same logic as Python. Since Go slices are mutable, we first create a copy of the input array before sorting so the original array remains unchanged.

Instead of bisect_right(), Go uses sort.Search(). We search for the first index where sortedNums[i] > value, which gives us the starting point of strictly greater elements.

Go integers are sufficient for this problem because the answer never exceeds n, and n ≤ 10^5, well within integer limits.

Worked Examples

Example 1

Input:

nums = [3,1,2]
k = 1

First, sort the array:

sorted_nums = [1,2,3]

Element	First Greater Index	Greater Elements	Qualified?
3	3	0	No
1	1	2	Yes
2	2	1	Yes

Final answer:

2

Example 2

Input:

nums = [5,5,5]
k = 2

Sorted array:

[5,5,5]

Element	First Greater Index	Greater Elements	Qualified?
5	3	0	No
5	3	0	No
5	3	0	No

Final answer:

0

Additional Example

Input:

nums = [1,2,3,4]
k = 2

Sorted array:

[1,2,3,4]

Element	First Greater Index	Greater Elements	Qualified?
1	1	3	Yes
2	2	2	Yes
3	3	1	No
4	4	0	No

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting takes O(n log n) and each of the n binary searches takes O(log n)
Space	O(n)	We store a sorted copy of the array

The dominant cost comes from sorting the array and performing binary search for every element. Since both contribute logarithmic factors, the total complexity remains O(n log n), which is efficient enough for n = 100,000.

Test Cases

solution = Solution()

assert solution.countElements([3, 1, 2], 1) == 2  # Example 1
assert solution.countElements([5, 5, 5], 2) == 0  # Example 2

assert solution.countElements([1], 0) == 1  # Single element, k = 0
assert solution.countElements([1, 2, 3, 4], 2) == 2  # Increasing order
assert solution.countElements([4, 3, 2, 1], 2) == 2  # Decreasing order
assert solution.countElements([1, 1, 1, 2], 1) == 3  # Duplicates with one larger
assert solution.countElements([2, 2, 3, 3, 4], 2) == 2  # Mixed duplicates
assert solution.countElements([10, 20, 30], 0) == 3  # k = 0, all qualify
assert solution.countElements([1, 2, 3], 2) == 1  # Only smallest qualifies
assert solution.countElements([1000000000, 1], 1) == 1  # Large values
assert solution.countElements([7, 7, 7, 7], 1) == 0  # All identical
assert solution.countElements([1, 2, 2, 2, 5], 1) == 4  # Multiple duplicates

Test	Why
[3,1,2], k=1	Validates the first example
[5,5,5], k=2	Validates equal values do not count as greater
[1], k=0	Smallest valid input
[1,2,3,4], k=2	Tests increasing order
[4,3,2,1], k=2	Tests decreasing order
[1,1,1,2], k=1	Verifies duplicate handling
[2,2,3,3,4], k=2	Mixed duplicates and thresholds
[10,20,30], k=0	Ensures all elements qualify for k = 0
[1,2,3], k=2	Verifies exact threshold behavior
[1000000000,1], k=1	Tests large integer values
[7,7,7,7], k=1	Ensures equal values are not counted
[1,2,2,2,5], k=1	Tests multiple duplicate groups

Edge Cases

Case 1, k = 0

When k equals zero, every element automatically qualifies because every element trivially has at least zero greater values.

A buggy implementation might accidentally exclude the maximum element because it has no larger values. However, since the condition is greater_count >= k, and k = 0, every element is correctly counted.

Case 2, All Elements Are Equal

Consider:

nums = [5,5,5]

Since the comparison is strictly greater, equal values do not contribute to the count.

A common mistake is accidentally treating equal values as valid using >= instead of >. Our implementation avoids this by using bisect_right() in Python and sortedNums[i] > value in Go, which guarantees only strictly larger values are counted.

Case 3, Large Numbers and Large Arrays

The constraints allow values up to 10^9 and arrays up to 10^5 elements.

A brute-force solution would perform up to 10^10 comparisons in the worst case, which is impractical. Our O(n log n) approach scales efficiently because sorting and binary search remain fast even for the maximum input size.

Case 4, Duplicate Values Around the Threshold

Consider:

nums = [2,2,3,3,4]
k = 2

The value 2 has three greater elements, while 3 has only one greater element.

Incorrect handling of duplicates may overcount or undercount greater values. By finding the first strictly greater index after duplicates, the implementation computes the exact number of larger elements every time.