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
- Let
mxbe the maximum of the whole array. Only the occurrences ofmxmatter. - Maintain a window and a count of
mxoccurrences inside it, shrinking from the left while the count is at leastk. - After shrinking, the minimal window containing
koccurrences ofmxis[l - 1, r], so every start in[0, l - 1]yields a valid subarray -- contributinglsubarrays for this right endpoint. - Summing
lover 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 isl. - Shrinking while
cnt > kinstead ofcnt >= k: the loop must reduce the count belowkso thatl - 1marks 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 oflhandles that automatically.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner