2958. Length of Longest Subarray With at Most K Frequency

Array
Hash Table
Sliding Window

TIME

O(n)

SPACE

O(n)

Intuition

The "good" property is monotone under shrinking: if a window satisfies "every frequency <= k", so does any sub-window of it. That's exactly the condition for a two-pointer sliding window, grow the right end greedily, and whenever the window breaks the rule, shrink from the left until it holds again.

Only one element can ever break the rule at a time: the one just added. So the shrink loop just needs to bring that element's count back down to k.

Approach

Keep a hash map freq of counts inside the current window, and a left pointer left.
For each right index r:
- Increment freq[nums[r]].
- While freq[nums[r]] > k, decrement freq[nums[left]] and advance left.
- Update the answer with r - left + 1.
Return the largest window seen.

Each index enters and leaves the window at most once, so the total work is linear.

Complexity

Time: O(n), amortized; left only moves forward
Space: O(n), the frequency map

Edge Cases

All identical values (Example 3) → answer is exactly k
k >= n → the whole array is good → answer n
k = 1 → longest run of pairwise-distinct values
Values up to 10^9 → use a hash map, not a fixed array
The answer is always at least 1 since k >= 1

Code

from typing import List
from collections import defaultdict


class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        """
        2958. Length of Longest Subarray With at Most K Frequency
        Time: O(n)
        Space: O(n)
        """
        freq = defaultdict(int)
        left = 0
        best = 0

        for r, x in enumerate(nums):
            freq[x] += 1
            # only the just-added value can violate the limit
            while freq[x] > k:
                freq[nums[left]] -= 1
                left += 1
            best = max(best, r - left + 1)

        return best

import java.util.HashMap;
import java.util.Map;

/**
 * 2958. Length of Longest Subarray With at Most K Frequency
 * Time: O(n)
 * Space: O(n)
 */
class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        int left = 0, best = 0;

        for (int r = 0; r < nums.length; r++) {
            int x = nums[r];
            freq.merge(x, 1, Integer::sum);
            // only the just-added value can violate the limit
            while (freq.get(x) > k) {
                freq.merge(nums[left], -1, Integer::sum);
                left++;
            }
            best = Math.max(best, r - left + 1);
        }

        return best;
    }
}