[Leetcode] 2962. Count Subarrays Where Max Element Appears at Least K Times

https://leetcode.com/problems/count-subarrays-where-max-element-appears-at-least-k-times/description/?envType=daily-question&envId=2025-04-29

initial

if u think its intutive to think of a pattern. Once we see a subarray that has k ore more maxium elements, that is a valid case. That means the rest of the subarrays from left to right+1, right+2 to right+n will be valid too cuz the original left to right subarray already has that valid condition of having k or more max elements.

impt!!!

1) But i tried implementing moving the right pointer via while loop but I did

while(right<n && left<right){

this is always false cuz left and right is 0 at the start! But I was worried that left poitner might overtake the right pointer.

But that will not happen cuz while right pointer moves for every iteration, left pointer will only move in the condition of count>=k. So u dont have to worry

2) u have to make answer type as long or else overflow will happen and u will not get right ans if values that u r adding exceeds the max value of integer

3) "at least k occurrences" so u should say while(count>=k), not while(count==k)

sol

u can just use a for loop too

import java.util.*;
class Solution {
    public long countSubarrays(int[] nums, int k) {
        int n = nums.length;
        int target=0;
        for(int i:nums){
            target=Math.max(target,i);
        }
        int left=0,right=0;
        int count=0;
        long ans=0;
        while(right<n){
            if(nums[right]==target) count+=1;
            while(count>=k){
                ans+=n-right;
                if(nums[left]==target){
                    count-=1;
                } 
                left+=1;
            }
            right+=1;
        }
        return ans;
    }
}

complexity

n time
1 space