⚡Flashcard Drill➔
NeetCode #250LC-2962MediumSliding Window
← Back to All Problems

#250 · #2962 · Count Subarrays Where Max Element Appears at Least K Times(统计最大元素出现至少 K 次的子数组)

📌 Problem Statement & Constraints

You are given an integer array nums and a positive integer k. Return the number of subarrays in which the maximum element of nums appears at least k times. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^9, 1 <= k <= nums.length.

💡 Core Algorithmic Approaches

  1. Let mx be the maximum of the whole array. Only the occurrences of mx matter.
  2. Maintain a window and a count of mx occurrences inside it, shrinking from the left while the count is at least k.
  3. After shrinking, the minimal window containing k occurrences of mx is [l - 1, r], so every start in [0, l - 1] yields a valid subarray -- contributing l subarrays for this right endpoint.
  4. Summing l over all right endpoints gives the answer.

💻 Benchmark Python3 Implementation

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        mx = max(nums)
        l = 0
        cnt = 0                        # occurrences of mx in the window
        res = 0
        for r, x in enumerate(nums):
            if x == mx:
                cnt += 1
            while cnt >= k:            # shrink to the minimal valid window
                if nums[l] == mx:
                    cnt -= 1
                l += 1
            # after shrinking, starts in [0, l-1] all give k occurrences
            res += l
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each pointer moves monotonically.
💾 Space Complexity
O(1): two scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Adding 1 per right endpoint instead of l: every valid start position yields a distinct subarray, so the contribution is l.
  • Shrinking while cnt > k instead of cnt >= k: the loop must reduce the count below k so that l - 1 marks the minimal valid window's start.
  • Recomputing max(nums) inside the loop: the global maximum never changes, so compute it once.
  • Counting subarrays where the maximum appears exactly k times: the condition is *at least* k, and the accumulation of l handles that automatically.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems