Problem of The Day: Count Subarrays Where Max Element Appears at Least K Times

Problem Statement

leetcode problem link

Intuition

We need to find the number of subarrays where the maximum element appears exactly k times.
Since the maximum value of the entire array is fixed, we can track how many times it appears within a sliding window to efficiently find valid subarrays.

Approach

• First, calculate the maximum value max_val in the array.
• Use two pointers (start and end) to form a sliding window:
  • Move end forward through the array.
  • Whenever nums[end] == max_val, increase count.
• When count == k, it means the current window [start, end] contains exactly k occurrences of max_val.
  • Important: Once we have a valid window, any subarray that starts at start or later and ends at end (or later) will still have exactly k max_val values (because end is fixed at the moment).
  • Since end can be extended to N-1 without changing the count, the number of valid subarrays is (N - end).
• After counting, shrink the window from the left by moving start, and decrease count if nums[start] == max_val.

Why (N - end)?

When we find a valid window where the number of max_val is exactly k, the subarrays:

• [start, end]
• [start+1, end]
• [start+2, end]
• …
• and so on, up to the end of the array will all be valid without changing the number of max_val.
  Thus, there are (N - end) valid subarrays for the current start.

Complexity

• Time complexity:
  \(O(n)\)
  Both start and end pointers move from left to right across the array, each visiting each element at most once.

• Space complexity:
  \(O(1)\)
  We only use a few extra integer variables.

Code

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        res = 0
        start = 0
        N = len(nums)
        count = 0
        max_val = max(nums)
        for end in range(N):
            count += 1 if nums[end] == max_val else 0
            while count == k and start <= end:
                res += (N - end)
                count -= 1 if nums[start] == max_val else 0
                start += 1
        return res

Editorial

Approach 1: Sliding Window

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        max_element = max(nums)
        ans = start = max_elements_in_window = 0

        for end in range(len(nums)):
            if nums[end] == max_element:
                max_elements_in_window += 1
            while max_elements_in_window == k:
                if nums[start] == max_element:
                    max_elements_in_window -= 1
                start += 1
            ans += start
        return ans