2962. Count-Subarrays-Where-Max-Element-Appears-At-Least-K-Times

Classic sliding window problem, I feel like we’ve had a lot of sliding window this month.

In our window, we keep track of the number of max element inside the current window. We extend the window (increment r) until this number is equal to k. Then the number of valid subarrays starting at l is equal to len(nums) - r + 1 and we can move onto the next l. Just the classic sliding window pattern…

We can return the total number of valid subarrays once we go through all possible l.

class Solution(object):
    def countSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        n = len(nums)
        maximum_element = max(nums)
        r = 0
        count = 0
        res = 0
        for l in range(n):
            if l > 0:
                if nums[l - 1] == maximum_element:
                    count -= 1
            while r < len(nums) and count < k:
                if nums[r] == maximum_element:
                    count += 1
                r += 1
            if count >= k:
                res += n - r + 1
        return res

Time Complexity: O(n)

Space Complexity: O(1)

Time Taken: forgot to keep track