Length of Longest Subarray With at Most K Frequency

How it works

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.

Steps

1. Track cnt, the count of elements whose frequency exceeds k.
2. For each right pointer, increment the element's frequency and update cnt if it just exceeded k.
3. 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.
4. The window size never shrinks, so after processing all elements, the answer is len(nums) - l.

Complexity

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

Things to watch for

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.

from typing import List
from collections import defaultdict

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

class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        int l = 0, cnt = 0; // count of numbers with freq > k
        for (int r = 0; r < nums.size(); r++) {
            count[nums[r]]++;
            cnt += count[nums[r]] > k;
            if (cnt > 0) {
                cnt -= count[nums[l]] > k;
                count[nums[l]]--;
                l++;
            }
        }
        return nums.size() - l;
    }
};