Count Subarrays Where Max Element Appears at Least K Times — LeetCode 2962 Python Solution

The problem

You are given an integer array nums and a positive integer k. Return the number of subarrays where the maximum element of nums appears at least k times in that subarray.

Example

Input

nums = [1,3,2,3,3], k = 2

Output

6

Explanation

The subarrays that contain the element 3 at least 2 times are: [1,3,2,3], [1,3,2,3,3], [3,2,3], [3,2,3,3], [2,3,3] and [3,3].

Python solution

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        mx = max(nums)
        n = len(nums)
        ans = cnt = j = 0
        for x in nums:
            while j < n and cnt < k:
                cnt += nums[j] == mx
                j += 1
            if cnt < k:
                break
            ans += n - j + 1
            cnt -= x == mx
        return ans

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2962. Count Subarrays Where Max Element Appears at Least K Times is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Sliding Window.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems