Problem Summary

You’re given an integer array nums and a number k. Your task is to count the number of subarrays where the maximum element of the entire array appears at least k times.

Input: nums = [1, 3, 2, 3, 3], k = 2  
Output: 6

Sliding Window to the Rescue

This is a classic case where brute force (O(n²)) would time out. The key to optimizing it is using a sliding window, but only once you’ve recognized the two essential insights:

1. We only care about the global maximum in nums.
2. We can count all valid subarrays ending at right efficiently using the formula (n - right).

Let’s look at the clean and optimized implementation:

class Solution {
    public long countSubarrays(int[] nums, int k) {
        // Find the maximum 
        // Traverse continous until the condition gets met
        int max = findMax(nums);
        
        int count = 0;
        long ans = 0;
        int left = 0;

        for(int right=0;right<nums.length;right++) {
            if (nums[right] == max) {
                count++;
            }

            while (count >= k) {
                ans += (nums.length-right);
                if (nums[left] == max) {
                    count--;
                }
                left++;
            }
        }
        return ans;

    }
    private int findMax(int []nums) {
        int max = Integer.MIN_VALUE;
        for(int num: nums){
            max = Math.max(max, num);
        }
        return max;
    }
}

Why (nums.length - right)?

Once a valid subarray [left, right] is found, any extension of it to the right (like [left, right+1], [left, right+2], etc.) will still be valid.

Hence, we can directly count all such subarrays in one shot instead of checking them one by one.

Time Complexity

• O(n) for traversing the array with two pointers.
• O(n) for findMax.

✅ Total: O(n) — efficient for large inputs.

Takeaway Patterns

This solution showcases a powerful pattern:

• Use sliding window when dealing with subarrays.
• When a condition becomes true (like count >= k), batch-count the subarrays to optimize.