NeetCode #249LC-2958MediumSliding Window
← Back to All Problems#249 · #2958 · Length of Longest Subarray With at Most K Frequency(最多 K 个重复元素的最长子数组)
📌 Problem Statement & Constraints
Given an array of integers
nums and an integer k, return the length of the longest subarray where the frequency of each element is at most k. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^9, 1 <= k <= nums.length.💡 Core Algorithmic Approaches
- Maintain a window whose every element's frequency is at most
k. - When the entering element's frequency exceeds
k, shrink from the left until it is back within budget. - The window length is the candidate answer.
- Only the entering element's count can newly violate the constraint, so the shrink loop condition can be checked against that single element.
💻 Benchmark Python3 Implementation
class Solution:
def maxSubarrayLength(self, nums: List[int], k: int) -> int:
from collections import defaultdict
cnt = defaultdict(int)
l = 0
best = 0
for r, x in enumerate(nums):
cnt[x] += 1
while cnt[x] > k: # only the entering element can violate
cnt[nums[l]] -= 1
l += 1
best = max(best, r - l + 1)
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each element enters and leaves the window at most once.
💾 Space Complexity
O(n) for the frequency map in the worst case.
⚠️ Interview Pitfalls & Follow-ups
- Checking all frequencies in the shrink condition: only the entering element's count can newly exceed
k, so checkingcnt[x]alone suffices and keeps the loop O(1) per step. - Shrinking until
cnt[x] == k: the condition iscnt[x] > k, so the loop must run while it exceedsk. - Deleting zero-count keys: unnecessary here, since the constraint is per-element rather than on the number of distinct values.
- Using a set: multiplicities are essential, so a count map is required.
⚡
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