Count Subarrays Where Max Element Appears at Least K Times

How it works

We maintain a sliding window containing exactly k indices of the max element. As we scan through the array, whenever we encounter the max element, we add its index to a queue. When the queue has more than k indices, we remove the oldest one. Whenever we have exactly k max element indices in our window, all positions from 0 to the first index in the queue are valid starting points for subarrays ending at the current position.

Steps

1. Find the maximum element and create an empty queue for indices.
2. For each index i in the array:
   • If nums[i] equals the max element, add i to the queue.
   • If the queue size exceeds k, remove the front element.
   • If the queue size equals k, add (front index + 1) to the result.
3. Return the total count.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Using Subarray Maximum Instead of Array Maximum

The problem asks for subarrays where the array's maximum element appears at least k times, not subarrays where the subarray's maximum appears k times. You must first find the global maximum of the entire array, then count its occurrences.

Off-by-One Error in Counting Valid Subarrays

When using the sliding window approach, a common mistake is miscounting the number of valid left endpoints. If the window [l, r] has exactly k occurrences of the max element with the max at position l, valid starting positions are 0 through l (inclusive), giving l + 1 subarrays, not l.

Integer Overflow with Large Arrays

The result can be very large (up to n * (n + 1) / 2 for an array of size n). Using int instead of long in languages like Java or C++ will cause overflow for large inputs. Always use long long or long for the result variable.

from typing import List
from collections import deque

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        max_n = max(nums)
        max_indexes = deque()
        res = 0

        for i, num in enumerate(nums):
            if num == max_n:
                max_indexes.append(i)

            if len(max_indexes) > k:
                max_indexes.popleft()

            if len(max_indexes) == k:
                res += max_indexes[0] + 1

        return res

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int maxN = *max_element(nums.begin(), nums.end());
        queue<int> maxIndexes;
        long long res = 0;

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == maxN) {
                maxIndexes.push(i);
            }

            if (maxIndexes.size() > k) {
                maxIndexes.pop();
            }

            if (maxIndexes.size() == k) {
                res += maxIndexes.front() + 1;
            }
        }

        return res;
    }
};