Count Subarrays Where Max Element Appears at Least K Times

Leetcode Problem:

• Count Subarrays Where Max Element Appears at Least K Times

Summary

• The problem requires finding the number of subarrays in a given array where the maximum element appears at least k times.

Approach

• The approach used is to first identify the maximum element and its corresponding subarray
• Then, we iterate over the subarray and count the number of subarrays that contain the maximum element at least k times.

Complexity

• O(n), where n is the size of the input array.

Explanation

• The solution first creates a vector to store the indices of the maximum element in the subarray
• It then iterates over the array to find the maximum element and its indices
• After that, it calculates the number of subarrays that contain the maximum element at least k times by iterating over the vector and counting the subarrays.

Solution Code:

class Solution {
public:
    vector v;
    long long countSubarrays(vector& nums, int k) {
        int maxV = 0;
        for(int i = 0 ; i < nums.size(); i++){
            if(maxV < nums[i]){
                maxV = nums[i];
                v.clear();
                v.push_back(i);
            } else if (maxV == nums[i]){
                v.push_back(i);
            }
        }
        v.push_back(nums.size());
        
        long long ans = 0;
        for(int i = k-1; i < v.size()-1; i++){
            long long r = v[i];
            long long l = v[i - k+1];
            ans += (l+1) * (v[i+1]-r);
        }
        return ans;
    }
};