Problem Statement in English

You’re given an integer array nums and an integer k. Your task is to count the number of contiguous subarrays where the maximum element appears at least k times.

Approach

This is a standard sliding window problem. All you really need is a hashmap.

Solution in Python


class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        hm = defaultdict(int)
        res = l = 0
        t = max(nums)
        LEN = len(nums)

        for r in range(LEN):
            hm[nums[r]] += 1

            while hm[t] >= k:
                res += LEN - r

                hm[nums[l]] -= 1
                l += 1

        return res

Complexity

  • Time: O(n)O(n)
    Since we iterate over the array once.

  • Space: O(n)O(n)
    Since we maintain a hasmap with the count of elements in the array.

And we are done.