Length of Longest Subarray With at Most K Frequency Solution
Length of Longest Subarray With at Most K Frequency solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Length of Longest Subarray With at Most K Frequency is a medium coding problem on arrays, hash table and sliding window, asked in Amazon, Google and Zomato interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sliding Window
- Asked at: Amazon, Google, Zomato
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A subarray is good when every value in it appears at most k times.
Return the length of the longest good subarray of nums.
Example 1
Input: nums = [1,2,3,1,2,3,1,2], k = 2
Output: 6
Explanation: [1,2,3,1,2,3] has each of 1, 2 and 3 twice.
Example 2
Input: nums = [1,2,1,2,1,2,1,2], k = 1
Output: 2
Example 3
Input: nums = [5,5,5,5,5,5,5], k = 4
Output: 4
Constraints
1 <= nums.length <= 1000001 <= nums[i] <= 10000000001 <= k <= nums.length
Hints for Length of Longest Subarray With at Most K Frequency
Hint 1
Removing elements can only lower every frequency, so 'good' is monotone in the left edge.
Hint 2
Only the value just added can break the invariant — no need to scan every frequency.
Hint 3
Shrink until that one value is back within
k.
How to solve Length of Longest Subarray With at Most K Frequency
A standard variable window. When a new element pushes its own frequency above k, pull the left edge in until it drops back. No other value can have become too frequent, so one check per step is enough.
Approach
- Add
nums[r]to the tally. - While its count exceeds
k, removenums[l]from the tally and advancel. - Record the window length.
Why it works
The only frequency that changes on the right is the incoming value's, so it is the only one that can violate the bound. Shrinking never raises a frequency, so the valid left edges for each right edge form a suffix — hence a single forward-moving left pointer, linear overall.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Re-checking every value's frequency turns each step linear and the whole scan quadratic.
- The shrink loop must test the incoming value's count, not the outgoing one's.
- Values reach
10^9, so a hash map is needed rather than a direct-indexed array.
Reference solution
Python
from typing import List
def maxSubarrayLength(nums: List[int], k: int) -> int:
cnt = {}
l = 0
best = 0
for r, v in enumerate(nums):
cnt[v] = cnt.get(v, 0) + 1
while cnt[v] > k:
cnt[nums[l]] -= 1
l += 1
best = max(best, r - l + 1)
return bestJava
public static int maxSubarrayLength(int[] nums, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
int l = 0, best = 0;
for (int r = 0; r < nums.length; r++) {
int v = nums[r];
cnt.merge(v, 1, Integer::sum);
while (cnt.get(v) > k) {
cnt.merge(nums[l], -1, Integer::sum);
l++;
}
best = Math.max(best, r - l + 1);
}
return best;
}C++
int maxSubarrayLength(vector<int>& nums, int k) {
unordered_map<int, int> cnt;
int l = 0, best = 0;
for (int r = 0; r < (int) nums.size(); r++) {
int v = nums[r];
cnt[v]++;
while (cnt[v] > k) {
cnt[nums[l]]--;
l++;
}
best = max(best, r - l + 1);
}
return best;
}JavaScript
var maxSubarrayLength = function(nums, k) {
var cnt = {};
var l = 0, best = 0;
for (var r = 0; r < nums.length; r++) {
var v = nums[r];
cnt[v] = (cnt[v] || 0) + 1;
while (cnt[v] > k) { cnt[nums[l]]--; l++; }
if (r - l + 1 > best) best = r - l + 1;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets