Count Subarrays Where Max Element Appears at Least K Times

Share

Count subarrays where the maximum element appears at least k times.

Example 1
Input: nums=[1,3,2,3,3], k=2 → Output: 6
Example 2
Input: nums=[1,4,2,1], k=3 → Output: 0

Solution Approach

Sliding window: find minimum valid window where max appears k times, then count subarrays.

  • Find global maximum
  • Sliding window tracking occurrences of max in window
  • When count >= k: all subarrays from [left..right] to [left..n-1] are valid
  • Shrink window, advance left
  • Return total count
Java
public long countSubarrays(int[] nums, int k) {
    int max = Arrays.stream(nums).max().getAsInt();
    long count = 0;
    int left = 0, maxCount = 0;
    for (int right = 0; right < nums.length; right++) {
        if (nums[right] == max) maxCount++;
        while (maxCount >= k) {
            count += nums.length - right;
            if (nums[left] == max) maxCount--;
            left++;
        }
    }
    return count;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)