Welcome to Subscribe On Youtube

3759. Count Elements With at Least K Greater Values

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.

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

Solutions

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 \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 $\textit{nums}$.

  • class Solution {
    public int countElements(int[] nums, int k) {
        int n = nums.length;
        if (k == 0) {
            return n;
        }
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < n - k; ++i) {
            if (nums[n - k] > nums[i]) {
                ++ans;
            }
        }
        return ans;
    }
}


  • class Solution {
public:
    int countElements(vector<int>& nums, int k) {
        int n = nums.size();
        if (k == 0) {
            return n;
        }
        ranges::sort(nums);
        int ans = 0;
        for (int i = 0; i < n - k; ++i) {
            if (nums[n - k] > nums[i]) {
                ++ans;
            }
        }
        return ans;
    }
};


  • class Solution:
    def countElements(self, nums: List[int], k: int) -> int:
        n = len(nums)
        if k == 0:
            return n
        nums.sort()
        return sum(nums[n - k] > nums[i] for i in range(n - k))


  • func countElements(nums []int, k int) int {
	n := len(nums)
	if k == 0 {
		return n
	}
	sort.Ints(nums)
	ans := 0
	for i := 0; i < n-k; i++ {
		if nums[n-k] > nums[i] {
			ans++
		}
	}
	return ans
}


  • function countElements(nums: number[], k: number): number {
    const n = nums.length;
    if (k === 0) {
        return n;
    }
    nums.sort((a, b) => a - b);
    let ans = 0;
    for (let i = 0; i < n - k; ++i) {
        if (nums[n - k] > nums[i]) {
            ++ans;
        }
    }
    return ans;
}

All Problems

All Solutions