Length of Longest Subarray With at Most K Frequency - Solution & Explanation
Problem Statement
You are given an integer array nums and an integer k.
The frequency of an element x is the number of times it occurs in an array.
An array is called good if the frequency of each element in this array is less than or equal to k.
Return the length of the longest good subarray of nums.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,2,3,1,2,3,1,2], k = 2 Output: 6 Explanation: 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 Explanation: 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 Explanation: 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 <= 1051 <= nums[i] <= 1091 <= k <= nums.length
Approach Overview
Problem Overview: Given an integer array nums and an integer k, find the length of the longest contiguous subarray where every number appears at most k times. The constraint applies to each distinct value inside the chosen window.
Approach 1: Sliding Window with Frequency Map (O(n) time, O(n) space)
This problem fits the classic sliding window pattern on arrays. Maintain two pointers left and right representing the current window and track element counts using a hash map. Expand the window by moving right and increment the frequency of nums[right]. If the frequency exceeds k, the window becomes invalid. Move left forward while decrementing counts until the constraint is restored.
At every step, the window represents a valid subarray where each value appears at most k times. Track the maximum window size using right - left + 1. Each element enters and leaves the window at most once, which keeps the total runtime linear. The frequency tracking uses a hash map from the hash table family, making updates and lookups constant time on average.
This approach works because the constraint is monotonic with respect to window expansion. Once a value appears more than k times, shrinking from the left is the only operation needed to restore validity. The algorithm scans the array once and dynamically maintains the best answer.
Approach 2: Binary Search Over Subarray Length (O(n log n) time, O(n) space)
Another way to view the problem is as a decision question: for a given length L, does any subarray of size L satisfy the frequency constraint? Because larger valid subarrays imply smaller ones are also valid, the answer space is monotonic. This allows binary search over the possible length range from 1 to n.
For each candidate length, scan the array using a fixed-size window and maintain a frequency map. When the window grows beyond L, decrement the frequency of the outgoing element. Track whether any window maintains all frequencies ≤ k. If a valid window exists, increase the search range; otherwise decrease it.
This method separates the validation logic from the optimization step, which can make reasoning easier in some scenarios. However, every binary search step performs a full linear scan, giving O(n log n) time complexity.
Recommended for interviews: The sliding window with a frequency map is the expected solution. It demonstrates understanding of window expansion, constraint maintenance, and hash-based counting in linear time. Binary search shows alternative thinking, but interviewers usually look for the O(n) sliding window implementation.
Approach 1: Sliding Window with Frequency Map
Use a sliding window technique to find the longest subarray that satisfies the condition where no element occurs more than k times. You can maintain a frequency map that tracks the count of each element in the current window.
This C solution uses a sliding window over the array nums. The frequency of each element in the window is stored in an array frequency. The window [start, end] is adjusted to keep all frequencies not exceeding k. We resize our window by incrementing start when an element's frequency exceeds k.
Complexity
Time Complexity: O(n) where n is the number of elements in nums, as each index is visited at most twice.
Space Complexity: O(m), where m is the maximum element value in nums representing the size of the frequency array.
Approach 2: Binary Search Over Subarray Length
A different approach is to use binary search to determine the maximum subarray length. The problem translates to searching for the maximum length for which a good subarray exists, using a helper function that verifies subarray validity in O(n) time.
This C approach involves a binary search to deduce the maximum length of a subarray fulfilling the condition, making use of a helper function. The helper function checks if there exists a good subarray of that length, leveraging frequency arrays similarly to a sliding window.
Complexity
Time Complexity: O(n log n) due to the binary search layers and inner check iteration.
Space Complexity: O(m) for the frequency array, where m is the maximum element value.
Approach 3: 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.
Next, we iterate over each element x in the array nums. For each element x, we increment the occurrence count of x, then check if the current subarray meets the requirements. If the current subarray does not meet the requirements, we move the pointer j one step to the right, and decrement the occurrence count of nums[j], until the current subarray meets the requirements. Then we update the answer ans = max(ans, i - j + 1). Continue the iteration until i reaches the end of the array.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window with Frequency Map | Time Complexity: |
| Binary Search Over Subarray Length | Time Complexity: |
| Two Pointers | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Frequency Map | O(n) | O(n) | Best general solution for arrays where element frequency must stay within a limit |
| Binary Search Over Subarray Length | O(n log n) | O(n) | Useful when the answer space is monotonic and you want a clear separation between validation and search |
Video Solution
Length of Longest Subarray With at Most K Frequency | 2 Ways | Leetcode 2958 | codestorywithMIK • codestorywithMIK • 13,029 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Length of Longest Subarray With at Most K Frequency easy or hard?
Length of Longest Subarray With at Most K Frequency Python/Java solution
How to solve Length of Longest Subarray With at Most K Frequency in O(n)?
What is the best approach for Length of Longest Subarray With at Most K Frequency?
Is Length of Longest Subarray With at Most K Frequency asked at Google/Amazon/Meta?
What data structure is used in Length of Longest Subarray With at Most K Frequency?
What is the time complexity of Length of Longest Subarray With at Most K Frequency?
Ready to solve this problem?
Practice Length of Longest Subarray With at Most K Frequency with our built-in code editor and test cases.
Practice on FleetCode