How to Solve Length of Longest Subarray With at Most K Frequency

Use a sliding window with a hash map to track the frequency of elements in the current subarray. Expand the window to include new elements until any element exceeds k, then shrink from the left. The maximum window length observed during this process is the result.

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

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.

How GhostInterview Helps

• Automatically tracks element frequencies and identifies maximum valid subarrays using sliding window.
• Highlights off-by-one errors in window shrinking for subarrays exceeding k occurrences.
• Provides step-by-step visualization of frequency updates to ensure correct maximum length calculation.

Topic Pages

• Array
• Hash Table
• Sliding Window

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.