LeetCode 2958 - Length of Longest Subarray With at Most K Frequency

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sliding Window

Solution

Problem Understanding

The problem asks us to find the length of the longest contiguous subarray in an array of integers nums such that the frequency of every element in that subarray does not exceed a given integer k. In other words, in the resulting subarray, no number appears more than k times.

The input consists of an integer array nums and an integer k. The output is a single integer representing the length of the longest "good" subarray. A subarray is contiguous, meaning that we cannot skip elements, and it is "good" if no element appears more than k times.

Constraints give us important information about scale. nums.length can be up to 10^5, so a naive O(n^2) solution that examines all subarrays would be too slow. Values in nums can be as large as 10^9, so we cannot rely on counting via an array indexed by value; we need a hash map or dictionary. k is at least 1 and at most the array length.

Edge cases to consider include arrays where all elements are the same, arrays with distinct elements, small arrays of length 1, and cases where k equals 1 or the array length.

Approaches

The brute-force approach examines every possible subarray. For each subarray, we would count the frequency of each element and check if it exceeds k. If it does not, we track the maximum length seen. This approach is correct but inefficient because it involves O(n^2) subarray enumeration and O(n) frequency counting, resulting in O(n^3) time in the worst case. This is far too slow for n = 10^5.

The optimal approach leverages a sliding window combined with a frequency hash map. The key insight is that if a subarray is "good," any of its subarrays are also "good." We can expand the window to the right while keeping the frequency of each element in the window. If any element exceeds k, we shrink the window from the left until all frequencies are ≤ k. This maintains a valid "good" window at all times. The length of the largest such window is the answer. This approach uses O(n) time because each element is added and removed at most once, and O(n) space for the hash map.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(n)	Check every subarray and count element frequencies
Optimal	O(n)	O(n)	Sliding window with hash map to maintain element counts

Algorithm Walkthrough

Initialize a hash map freq to store the frequency of each element in the current window. Initialize two pointers left and right at 0. Also, initialize max_length to track the maximum window length.
Expand the window by moving right to the next element. Increment the frequency of nums[right] in the hash map.
After adding an element, check if its frequency exceeds k. If it does, the window is no longer "good." Shrink the window from the left by moving left forward and decrementing the frequencies of elements removed from the window. Continue shrinking until all frequencies are ≤ k.
After ensuring the current window is valid, update max_length as max(max_length, right - left + 1).
Repeat steps 2-4 until right reaches the end of the array.
Return max_length.

Why it works: The algorithm maintains the invariant that the current window [left, right] is always a "good" subarray. By expanding to the right and shrinking from the left only when necessary, we consider all possible valid subarrays efficiently. This guarantees that we will find the longest one.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        freq = defaultdict(int)
        left = 0
        max_length = 0
        
        for right in range(len(nums)):
            freq[nums[right]] += 1
            
            while freq[nums[right]] > k:
                freq[nums[left]] -= 1
                left += 1
            
            max_length = max(max_length, right - left + 1)
        
        return max_length

The Python implementation uses a defaultdict to automatically handle keys that are not yet in the dictionary. The outer loop expands the window, and the inner while loop ensures that no element exceeds frequency k. The maximum length is updated at every step to account for the current valid window.

Go Solution

func maxSubarrayLength(nums []int, k int) int {
    freq := make(map[int]int)
    left := 0
    maxLength := 0

    for right := 0; right < len(nums); right++ {
        freq[nums[right]]++

        for freq[nums[right]] > k {
            freq[nums[left]]--
            left++
        }

        if right-left+1 > maxLength {
            maxLength = right - left + 1
        }
    }

    return maxLength
}

In Go, we use a map to track frequencies. The logic mirrors the Python version. We increment frequencies when expanding the window, and decrement while shrinking from the left to maintain the "good" property.

Worked Examples

Example 1: nums = [1,2,3,1,2,3,1,2], k = 2

right	nums[right]	freq map	left	window length	max_length
0	1	{1:1}	0	1	1
1	2	{1:1,2:1}	0	2	2
2	3	{1:1,2:1,3:1}	0	3	3
3	1	{1:2,2:1,3:1}	0	4	4
4	2	{1:2,2:2,3:1}	0	5	5
5	3	{1:2,2:2,3:2}	0	6	6
6	1	{1:3,2:2,3:2}	0->1->2	6	6
7	2	{1:2,2:3,3:2}	2->3	5	6

Result: 6

Example 2: nums = [1,2,1,2,1,2,1,2], k = 1

The window alternates between [1,2] or [2,1] to keep frequency ≤ 1. The longest length is 2.

Example 3: nums = [5,5,5,5,5,5,5], k = 4

The frequency of 5 exceeds k at the fifth element. Shrink the window from the left. The longest subarray with frequency ≤ 4 is [5,5,5,5], length 4.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is added and removed at most once from the window
Space	O(n)	Hash map stores frequencies of elements in the current window, potentially all unique

The algorithm is efficient for the given constraints. n up to 10^5 is feasible with linear time complexity.

Test Cases

# Provided examples
assert Solution().maxSubarrayLength([1,2,3,1,2,3,1,2], 2) == 6
assert Solution().maxSubarrayLength([1,2,1,2,1,2,1,2], 1) == 2
assert Solution().maxSubarrayLength([5,5,5,5,5,5,5], 4) == 4

# Boundary tests
assert Solution().maxSubarrayLength([1], 1) == 1 # single element array
assert Solution().maxSubarrayLength([1,1,1,1], 4) == 4 # all same element, k equals length
assert Solution().maxSubarrayLength([1,2,3,4], 1) == 4 # all distinct elements, k = 1
assert Solution().maxSubarrayLength([1,1,2,2,3,3,4,4], 2) == 8 # repeated pairs, exactly k
assert Solution().maxSubarrayLength([1,2,2,2,3,3,3,3,4,4,4], 2) == 5 # mixed frequencies

Test	Why
Single element	Edge case of minimal array