Daily Question – 2962. Count Subarrays Where Max Element Appears at Least K Times

Description: https://leetcode.com/problems/count-subarrays-where-max-element-appears-at-least-k-times

Note:

This isn’t a difficult question, but I needed to read the description more carefully.

Initially, I misunderstood the question, thinking it was asking for the total number of subarrays in which a number appears at least ‘k’ times.

On my second attempt, I still misunderstood the question, interpreting it as asking for the total number of subarrays which maximum frequency in the ‘nums’ array where a number appears at least ‘k’ times.

Finally, after reading the discussion, I understood that the problem was asking for the number of subarrays where the maximum element of nums appears at least k times in that subarray.

The algorithm is quite straightforward. After identifying the maximum element in ‘nums’, use a sliding window approach to find the smallest subarray that meets the requirement.

Code:

class Solution {
    public long countSubarrays(int[] nums, int k) {
        if (nums.length < k ) return 0;
        int left = 0, right = 0, max = 0, maxKey = 0, boundary = nums.length, count = 0;
        long result = 0;
        for (int num : nums) if (num > maxKey) maxKey= num;
        for (right = 0; right< boundary; right++) {
            if (nums[right] == maxKey) count++;
            if (count == k) break;
        }
        result += boundary - right;
        while (right < boundary) {
            if (nums[left] == maxKey) {
                count--;
            }
            left++;
            while (count < k && right < boundary) {
                right++;
                if (right == boundary) break;
                if (nums[right] == maxKey) count++;
                if (count == k) break;
            }
            if (count == k) result += boundary - right;
        }
        return result;
    }
}

Simplify by ChatGPT:

We could use Arrays.stream to find the maxNum.

class Solution {
    public long countSubarrays(int[] nums, int k) {
        if (nums.length < k) return 0;
        
        int maxNum = Arrays.stream(nums).max().getAsInt();
        int left = 0, right = 0, count = 0;
        long result = 0;
        
        while (right < nums.length) {
            if (nums[right] == maxNum) count++;
            if (count == k) {
                result += nums.length - right;
                if (nums[left] == maxNum) count--;
                left++;
            }
            right++;
        }
        return result;
    }
}