Count subarrays where the maximum element appears at least k times.
Input: nums=[1,3,2,3,3], k=2 → Output: 6
Input: nums=[1,4,2,1], k=3 → Output: 0
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
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)