2958. Length of Longest Subarray With at Most K Frequency - Explanation

1. Brute Force

Intuition

The most direct approach is to examine every possible subarray and check if it satisfies the frequency constraint. For each starting position, we extend the subarray one element at a time, tracking element frequencies as we go. The moment any element appears more than k times, we stop extending and move to the next starting position.

Algorithm

Initialize res to track the maximum valid subarray length.
For each starting index i, create a frequency map and iterate through all ending indices j.
Increment the count for each element as we expand the window.
If any element's frequency exceeds k, break out of the inner loop.
Otherwise, update res with the current subarray length j - i + 1.
Return res after checking all subarrays.

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        n, res = len(nums), 0

        for i in range(n):
            count = defaultdict(int)
            for j in range(i, n):
                count[nums[j]] += 1
                if count[nums[j]] > k:
                    break
                res = max(res, j - i + 1)

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Sliding Window

Intuition

Instead of restarting from scratch for each position, we can maintain a sliding window that always represents a valid subarray. When adding an element causes a frequency violation, we shrink the window from the left until the constraint is satisfied again. This way, we only process each element twice at most: once when entering and once when leaving the window.

Algorithm

Use two pointers l (left) and r (right) to define the current window.
Maintain a hash map to track the frequency of each element in the window.
For each right pointer position, add the current element to the frequency map.
While the newly added element's frequency exceeds k, shrink the window by incrementing l and decrementing the corresponding frequency.
Update res with the current window size r - l + 1.
Return the maximum length found.

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        res = 0
        count = defaultdict(int)
        l = 0
        for r in range(len(nums)):
            count[nums[r]] += 1
            while count[nums[r]] > k:
                count[nums[l]] -= 1
                l += 1
            res = max(res, r - l + 1)
        return res

Time & Space Complexity

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

3. Sliding Window (Optimal)

Intuition

We can optimize further by observing that we only care about finding the maximum window size. Once we find a valid window of size w, we never need a smaller one. So instead of shrinking the window completely when invalid, we just slide it: move both left and right pointers by one. The window size either stays the same or grows, never shrinks. This guarantees we find the maximum valid window.

Algorithm

Track cnt, the count of elements whose frequency exceeds k.
For each right pointer, increment the element's frequency and update cnt if it just exceeded k.
If cnt > 0 (window is invalid), slide the window by moving the left pointer once. Before moving, check if the left element's frequency was above k and decrement cnt accordingly.
The window size never shrinks, so after processing all elements, the answer is len(nums) - l.

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        count = defaultdict(int)
        l = res = 0
        cnt = 0  # count of numbers with freq > k
        for r in range(len(nums)):
            count[nums[r]] += 1
            cnt += count[nums[r]] > k
            if cnt > 0:
                cnt -= count[nums[l]] > k
                count[nums[l]] -= 1
                l += 1
        return len(nums) - l

Time & Space Complexity

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

Common Pitfalls

Forgetting to Decrement Frequency When Shrinking the Window

When the left pointer moves, you must decrement the frequency count of the element being removed from the window. Failing to do this causes the frequency map to retain stale counts, leading to incorrect constraint checks and wrong answers.

Using the Wrong Comparison Operator for the Constraint

The problem asks for elements appearing "at most k times," meaning frequency should be <= k. Using < k instead of <= k (or > k for violation checks) will incorrectly shrink the window too early or allow invalid windows.

Not Updating the Result at the Right Time

In sliding window problems, update the maximum length after ensuring the window is valid, not before. Updating before shrinking the window can record an invalid window size, resulting in an answer that exceeds the actual longest valid subarray.