#2958

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Length of Longest Subarray With at Most K Frequency

Find the maximum length subarray where each number appears at most k times using array scanning and hash lookups.

Problem Statement

Given an integer array nums and an integer k, determine the length of the longest contiguous subarray in which no element appears more than k times. A subarray is valid if all element counts are less than or equal to k.

Return the length of this longest subarray. For example, with nums = [1,2,3,1,2,3,1,2] and k = 2, the answer is 6 because [1,2,3,1,2,3] is the longest valid subarray.

Examples

Example 1

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

Output: 6

The longest possible good subarray is [1,2,3,1,2,3] since the values 1, 2, and 3 occur at most twice in this subarray. Note that the subarrays [2,3,1,2,3,1] and [3,1,2,3,1,2] are also good. It can be shown that there are no good subarrays with length more than 6.

Example 2

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

Output: 2

The longest possible good subarray is [1,2] since the values 1 and 2 occur at most once in this subarray. Note that the subarray [2,1] is also good. It can be shown that there are no good subarrays with length more than 2.

Example 3

Input: nums = [5,5,5,5,5,5,5], k = 4

Output: 4

The longest possible good subarray is [5,5,5,5] since the value 5 occurs 4 times in this subarray. It can be shown that there are no good subarrays with length more than 4.

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= nums.length

Solution Approach

Sliding Window with Frequency Map

Initialize a left pointer and a hash map to store element counts. Move the right pointer forward, updating counts. If any count exceeds k, increment left until all counts are <= k. Track the maximum window length.

Optimize with Early Window Shrinking

Instead of checking all counts at each step, shrink the window only when the newly added element exceeds k. This avoids unnecessary recalculation and ensures linear time complexity.

Edge Case Handling

Handle cases where k = 1 or all elements are the same. Ensure the window logic correctly updates counts and does not miss subarrays starting at the first index or ending at the last index.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

Time complexity is O(N) because each element is added and removed from the hash map at most once. Space complexity is O(N) to store the frequency map in the worst case when all elements are unique.

What Interviewers Usually Probe

Are you correctly updating the frequency map when moving both left and right pointers?
Can you handle arrays where elements repeat more than k times immediately?
Have you considered edge cases like k = 1 or uniform arrays?

Common Pitfalls or Variants

Common pitfalls

Forgetting to decrement counts when shrinking the window leads to incorrect frequency tracking.
Assuming all elements can be included without checking frequency can overcount the window length.
Not handling subarrays at array boundaries can miss the maximum length.

Follow-up variants

Find the length of the longest subarray where exactly k occurrences of any element are allowed.
Compute the longest subarray with at most k distinct elements rather than frequency-based restriction.
Determine the maximum sum subarray where each number appears at most k times.

FAQ

What is the key idea behind Length of Longest Subarray With at Most K Frequency?

Use a sliding window combined with a hash map to track how many times each element occurs, shrinking the window when any count exceeds k.

Can this problem be solved without a hash map?

No efficient linear solution exists without tracking element counts, since you need to know if adding a new element exceeds k.

What happens when k = 1?

The algorithm reduces to finding the longest subarray with all unique elements, shrinking the window whenever a duplicate appears.

Is it necessary to check the frequency of all elements at every step?

No, only the newly added element's frequency needs checking, and the window shrinks until all counts are valid.

Does the array scanning plus hash lookup pattern apply to variations of this problem?

Yes, any problem that tracks element frequencies in a contiguous window benefits from this exact sliding window with hash map pattern.

terminal

Solution

Solution 1: Two Pointers

We can use two pointers $j$ and $i$ to represent the left and right endpoints of the subarray, initially both pointers point to the first element of the array.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        cnt = defaultdict(int)
        ans = j = 0
        for i, x in enumerate(nums):
            cnt[x] += 1
            while cnt[x] > k:
                cnt[nums[j]] -= 1
                j += 1
            ans = max(ans, i - j + 1)
        return ans

Continue Practicing

#2935 maximum strong pair xor ii #2932 maximum strong pair xor i #3013 divide an array into subarrays with minimum cost ii