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

Problem Link



1. Brute Force

Intuition

We need to count subarrays where the maximum element of the entire array appears at least k times. The simplest approach is to check every possible subarray by trying all starting and ending positions, counting occurrences of the maximum element in each subarray.

Algorithm

  1. Find the maximum element in the array.
  2. For each starting index i from 0 to n-1:
    • Initialize a counter for max element occurrences.
    • For each ending index j from i to n-1:
      • If nums[j] equals the max element, increment the counter.
      • If the counter is at least k, this subarray is valid; increment the result.
  3. Return the total count of valid subarrays.
class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n, res = len(nums), 0
        maxi = max(nums)

        for i in range(n):
            cnt = 0
            for j in range(i, n):
                if nums[j] == maxi:
                    cnt += 1

                if cnt >= k:
                    res += 1

        return res

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(1)O(1)

2. Variable Size Sliding Window

Intuition

Instead of checking all subarrays, we can use a sliding window. For each right endpoint, we find the smallest left endpoint such that the window contains exactly k occurrences of the max element with the max element at position l. All positions from 0 to l can serve as left endpoints for valid subarrays ending at r.

Algorithm

  1. Find the maximum element and initialize counters.
  2. Use two pointers l and r, both starting at 0.
  3. For each right pointer position:
    • If nums[r] is the max element, increment the count.
    • Shrink the window from the left while the count exceeds k, or while count equals k and the left element is not the max (to find the rightmost valid left position).
    • If count equals k, add (l + 1) to the result, representing all valid starting positions.
  4. Return the total count.
class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        max_n, max_cnt = max(nums), 0
        l = 0
        res = 0

        for r in range(len(nums)):
            if nums[r] == max_n:
                max_cnt += 1

            while max_cnt > k or (l <= r and max_cnt == k and nums[l] != max_n):
                if nums[l] == max_n:
                    max_cnt -= 1
                l += 1

            if max_cnt == k:
                res += l + 1

        return res

Time & Space Complexity

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

3. Variable Size Sliding Window (Optimal)

Intuition

We can simplify the sliding window by counting subarrays with fewer than k occurrences and subtracting from total, or equivalently, counting invalid prefixes. For each right endpoint, we maintain a window that has exactly k occurrences of the max element, then shrink it until we have fewer than k. The left pointer position tells us how many valid subarrays end at this right position.

Algorithm

  1. Find the maximum element and initialize counters.
  2. For each right pointer position:
    • If nums[r] is the max element, increment the count.
    • While count equals k:
      • If nums[l] is the max element, decrement the count.
      • Move l to the right.
    • Add l to the result (representing all valid starting positions from 0 to l-1).
  3. Return the total count.
class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        max_n, max_cnt = max(nums), 0
        l = res = 0

        for r in range(len(nums)):
            if nums[r] == max_n:
                max_cnt += 1
            while max_cnt == k:
                if nums[l] == max_n:
                    max_cnt -= 1
                l += 1
            res += l

        return res

Time & Space Complexity

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

4. Fixed Size Sliding Window + Math

Intuition

We can collect all indices where the max element appears and then use combinatorics. For each window of k consecutive max element positions, the number of valid subarrays can be computed by multiplying the number of possible left endpoints (positions before the first max in the window) by the number of possible right endpoints (positions from the last max to the end of the array).

Algorithm

  1. Find the maximum element and collect all indices where it appears.
  2. Add -1 at the beginning of the index list (as a sentinel for computing gaps).
  3. For each window of k consecutive indices in the list:
    • Calculate left choices: difference between current index and previous index.
    • Calculate right choices: distance from the last index in the window to the end.
    • Multiply these values and add to the result.
  4. Return the total count.
class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        max_n = max(nums)
        max_indexes = [-1]
        for i, num in enumerate(nums):
            if num == max_n:
                max_indexes.append(i)

        res = 0
        for i in range(1, len(max_indexes) - k + 1):
            cur = (max_indexes[i] - max_indexes[i - 1])
            cur *= (n - max_indexes[i + k - 1])
            res += cur

        return res

Time & Space Complexity

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

5. Fixed Size Sliding Window (Optimal)

Intuition

We maintain a sliding window containing exactly k indices of the max element. As we scan through the array, whenever we encounter the max element, we add its index to a queue. When the queue has more than k indices, we remove the oldest one. Whenever we have exactly k max element indices in our window, all positions from 0 to the first index in the queue are valid starting points for subarrays ending at the current position.

Algorithm

  1. Find the maximum element and create an empty queue for indices.
  2. For each index i in the array:
    • If nums[i] equals the max element, add i to the queue.
    • If the queue size exceeds k, remove the front element.
    • If the queue size equals k, add (front index + 1) to the result.
  3. Return the total count.
class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        max_n = max(nums)
        max_indexes = deque()
        res = 0

        for i, num in enumerate(nums):
            if num == max_n:
                max_indexes.append(i)

            if len(max_indexes) > k:
                max_indexes.popleft()

            if len(max_indexes) == k:
                res += max_indexes[0] + 1

        return res

Time & Space Complexity

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