Count Subarrays Where Max Element Appears at Least K Times

main.md

Question

Approach

I iterated through the array with a right pointer and maintained a left pointer to denote the start of the current window. As I moved the right pointer, I tracked how many times the current max value appeared in the window.

Each time the count of the max value reached at least k, I knew that all subarrays ending at this right and starting from any index ≤ left would be valid. So I added (left + 1) to the result.

If the count of the max fell below k, I shrank the window from the left until the condition was satisfied again.

Implementation

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        max_num = max(nums)
        count = 0
        freq = 0 
        left = 0
        
        for right in range(len(nums)):
            if nums[right] == max_num:
                freq += 1

            while freq >= k:
                count += len(nums) - right
                if nums[left] == max_num:
                    freq -= 1
                left += 1
        
        return count

Complexities

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