⚡Flashcard Drill➔
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

  1. Maintain a window whose every element's frequency is at most k.
  2. When the entering element's frequency exceeds k, shrink from the left until it is back within budget.
  3. The window length is the candidate answer.
  4. 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 checking cnt[x] alone suffices and keeps the loop O(1) per step.
  • Shrinking until cnt[x] == k: the condition is cnt[x] > k, so the loop must run while it exceeds k.
  • 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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems