Watch 10 video solutions for Length of Longest Subarray With at Most K Frequency, a medium level problem involving Array, Hash Table, Sliding Window. This walkthrough by NeetCodeIO has 12,373 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.lengthProblem 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 | 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 |