Tejav
#3759

Count Elements With at Least K Greater Values

Medium
ArrayBinary SearchDivide and ConquerSortingQuickselectHash MapArray
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n log n)
Space
O(1)
O(n)
💡

Intuition

Time O(n log n)Space O(n)

Sort the array and use binary search to efficiently count how many elements are greater than each unique value.

⚙️

Algorithm

3 steps
  1. 1Step 1: Sort the nums array.
  2. 2Step 2: For each unique value, use binary search to find the first index where elements are greater.
  3. 3Step 3: If the count of greater elements is at least k, add the frequency of that value to the total qualified count.
solution.py11 lines
1def countQualifyingElements(nums, k):
2    from bisect import bisect_right
3    nums.sort()
4    count = 0
5    n = len(nums)
6    unique_values = sorted(set(nums))
7    for val in unique_values:
8        greater_count = n - bisect_right(nums, val)
9        if greater_count >= k:
10            count += nums.count(val)
11    return count
ℹ

Complexity note: Sorting takes O(n log n) and counting unique values takes O(n).

  • 1Sorting helps in efficiently counting elements greater than a given value.
  • 2Using binary search reduces the time complexity significantly.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.