2962: Count-Subarrays-Where-Max-Element-Appears-at-Least-K-Times
Medium

table of contents

For this question, I decided to pursue a two-pointers / sliding window approach. The key to this question is to realise that, for every left index, if you find the minimum right index such that the maximum element of nums appears at least k times in the subarray, then that implies that for all indices greater than right, the same condition will still hold.

Therefore, once you find the minimum right index that satisfies the condition, you can add num.size() - r + 1 to your ans, before incrementing left again and repeating the whole cycle again.

code

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        // to find the MAXIMUM element of `nums`
        int mx = 0;
        for (int n : nums) {
            mx = max(mx, n);
        }

        // LEFT index, RIGHT index, COUNT of maximum elements in sliding window
        int l = 0, r = 0, count = 0;
        // the number of feasible subarrays
        long long ans = 0;

        // basically, we iterate until either
        // - `l` index reaches the end of the array
        // - either `r` index reaches the end of the array or the `count` < k
        // (the 2nd conditional is because `r` might have reached the end of the array
        //  but we can still increment `l` until COUNT < k)
        for (; l < nums.size() && (r < nums.size() || count == k);) {
            // for each `l`, increment `r` until
            // - either we reach the end of the array
            // - or we satisfy `count` == k
            for (; r < nums.size() && count < k; ++r) {
                if (nums[r] == mx) {
                    ++count;
                }
            }
            // then, if `count` == k, we can increment `ans` 
            // with all the possible right indices that satisfy the conditional
            if (count == k) {
                ans += nums.size()-r+1;
            }
            
            // now, to prepare to increment `l`, we can decrement count 
            // if `nums[l] == mx` since this value will not be present in our sliding window anymore
            if (nums[l] == mx) {
                --count;
            }
            ++l; // now we increment `l` and pray
        }
        return ans;
    }
};

complexity

time taken