Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The target is the maximum of the entire array, not the maximum of each subarray. For a fixed right endpoint, valid starting positions form a prefix: once a subarray contains at least k target occurrences, extending it to the left cannot invalidate it.

Approach

Find the global maximum. Move a right pointer through the array while counting target occurrences in the current window. Whenever the count reaches k, advance the left pointer, subtracting target occurrences that leave, until the count is below k again.

At this point, the window starting at left is invalid, while all starts from zero through left - 1 are valid for this right endpoint. Add left to the answer. The previous window had fewer than k occurrences, so one added element can raise the count only to k, matching the loop condition used in the code. Each pointer advances only forward.

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        target = max(nums)
        count = 0
        res = 0

        l = 0
        for r in range(0, n):
            #1. update count of max element
            if nums[r] == target: count += 1
            #2. update l until count < k
            while count == k:
                if nums[l] == target: count -= 1
                l += 1
            #3. add all subarrays from 0 to l
            res += l

        return res

Complexity analysis

Let n = nums.length. Time: O(n). Auxiliary space: O(1) in both versions.