Length of Longest Subarray With at Most K Frequency solution and explanation
Google
9 more videos on this problem
Length of Longest Subarray With at Most K Frequency | 2 Ways | Leetcode 2958 | codestorywithMIKcodestorywithMIK · 21:52 · 13K views
Length of Longest Subarray With at Most K Frequency - Leetcode 2958 - PythonNeetCodeIO · 8:02 · 12K views
2958. Length of Longest Subarray With at Most K Frequency | 2 Pointers | Sliding WindowAryan Mittal · 10:25 · 4K views
2958. Length of Longest Subarray With at Most K Frequency | leetcode daily challenge | DSA | ShashShashCode · 14:56 · 2K views
2958. Length of Longest Subarray With at Most K Frequency | LEETCODE BIWEEKLY 119 | 2 POINTERScode Explainer · 10:01 · 752 views
2958. Length of Longest Subarray With at Most K Frequency - Problem Solving بالعربيAhmed Elemam - أحمد الإمام · 38:09 · 726 views
2958. Length of Longest Subarray With at Most K Frequency (Leetcode Medium)Programming Live with Larry · 6:19 · 395 views
LeetCode Challenge: 2958. Length of Longest Subarray With at Most K Frequency | C++ | Sliding WindowSHWETA BHAGAT · 27:17 · 375 views
Leetcode | 2958. Length of Longest Subarray With at Most K Frequency | Medium | Java SolutionDeveloper Docs · 9:43 · 296 views
Length of Longest Subarray With at Most K Frequency - LeetCode 2958 - PythonAlpha-Code · 10:05 · 252 views
The problem
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.
def longest_good_subarray(nums, k):
from collections import defaultdict
freq = defaultdict(int)
start = 0
max_len = 0
for end in range(len(nums)):
freq[nums[end]] += 1
while freq[nums[end]] > k:
freq[nums[start]] -= 1
if freq[nums[start]] == 0:
del freq[nums[start]]
start += 1
max_len = max(max_len, end - start + 1)
return max_len
# Example usage
nums = [1, 2, 3, 1, 2, 3, 1, 2]
k = 2
print(longest_good_subarray(nums, k))import java.util.HashMap;
import java.util.Map;
public class LongestGoodSubarray {
public static int longestGoodSubarray(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
int start = 0, max_len = 0;
for (int end = 0; end < nums.length; end++) {
freq.put(nums[end], freq.getOrDefault(nums[end], 0) + 1);
while (freq.get(nums[end]) > k) {
freq.put(nums[start], freq.get(nums[start]) - 1);
if (freq.get(nums[start]) == 0) {
freq.remove(nums[start]);
}
start++;
}
max_len = Math.max(max_len, end - start + 1);
}
return max_len;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 1, 2, 3, 1, 2};
int k = 2;
System.out.println(longestGoodSubarray(nums, k));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int longestGoodSubarray(vector<int>& nums, int k) {
unordered_map<int, int> freq;
int start = 0, max_len = 0;
for (int end = 0; end < nums.size(); ++end) {
freq[nums[end]]++;
while (freq[nums[end]] > k) {
freq[nums[start]]--;
if (freq[nums[start]] == 0) {
freq.erase(nums[start]);
}
start++;
}
max_len = max(max_len, end - start + 1);
}
return max_len;
}
int main() {
vector<int> nums = {1, 2, 3, 1, 2, 3, 1, 2};
int k = 2;
cout << longestGoodSubarray(nums, k) << endl;
return 0;
}function longestGoodSubarray(nums, k) {
let freq = new Map();
let start = 0, max_len = 0;
for (let end = 0; end < nums.length; end++) {
freq.set(nums[end], (freq.get(nums[end]) || 0) + 1);
while (freq.get(nums[end]) > k) {
freq.set(nums[start], freq.get(nums[start]) - 1);
if (freq.get(nums[start]) === 0) {
freq.delete(nums[start]);
}
start++;
}
max_len = Math.max(max_len, end - start + 1);
}
return max_len;
}
const nums = [1, 2, 3, 1, 2, 3, 1, 2];
const k = 2;
console.log(longestGoodSubarray(nums, k));#include <stdio.h>
#include <stdlib.h>
int longestGoodSubarray(int* nums, int numsSize, int k) {
int start = 0, max_len = 0;
int* frequency = (int*)calloc(1000000001, sizeof(int));
int distinct = 0;
for (int end = 0; end < numsSize; end++) {
frequency[nums[end]]++;
if (frequency[nums[end]] == 1) {
distinct++;
}
while (frequency[nums[end]] > k) {
frequency[nums[start]]--;
if (frequency[nums[start]] == 0) {
distinct--;
}
start++;
}
if (frequency[nums[end]] <= k) {
max_len = (end - start + 1) > max_len ? (end - start + 1) : max_len;
}
}
free(frequency);
return max_len;
}
int main() {
int nums[] = {1, 2, 3, 1, 2, 3, 1, 2};
int k = 2;
int length = longestGoodSubarray(nums, 8, k);
printf("%d\n", length);
return 0;
}using System;
using System.Collections.Generic;
class Program {
public static int LongestGoodSubarray(int[] nums, int k) {
Dictionary<int, int> freq = new Dictionary<int, int>();
int start = 0, max_len = 0;
for (int end = 0; end < nums.Length; end++) {
if (freq.ContainsKey(nums[end]))
freq[nums[end]]++;
else
freq[nums[end]] = 1;
while (freq[nums[end]] > k) {
freq[nums[start]]--;
if (freq[nums[start]] == 0)
freq.Remove(nums[start]);
start++;
}
max_len = Math.Max(max_len, end - start + 1);
}
return max_len;
}
static void Main() {
int[] nums = {1, 2, 3, 1, 2, 3, 1, 2};
int k = 2;
Console.WriteLine(LongestGoodSubarray(nums, k));
}
}Using a Python defaultdict to manage element frequencies, this implementation applies the sliding window technique similarly. The start and end pointers are adjusted accordingly, and the maximum valid subarray length is recorded.
Time Complexity: O(n).
Space Complexity: O(n) due to the storage requirements of the frequency dictionary.
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.
def is_good_subarray(nums, subarray_size, k):
from collections import defaultdict
freq = defaultdict(int)
for i in range(subarray_size):
freq[nums[i]] += 1
if freq[nums[i]] > k:
return False
for i in range(subarray_size, len(nums)):
freq[nums[i]] += 1
if freq[nums[i]] > k:
return False
freq[nums[i - subarray_size]] -= 1
if freq[nums[i - subarray_size]] == 0:
del freq[nums[i - subarray_size]]
return True
def longest_good_subarray(nums, k):
low, high, answer = 1, len(nums), 0
while low <= high:
mid = low + (high - low) // 2
if is_good_subarray(nums, mid, k):
answer = mid
low = mid + 1
else:
high = mid - 1
return answer
nums = [1, 2, 3, 1, 2, 3, 1, 2]
k = 2
print(longest_good_subarray(nums, k))import java.util.HashMap;
import java.util.Map;
public class LongestGoodSubarrayBinarySearch {
public static boolean isGoodSubarray(int[] nums, int subarraySize, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int i = 0; i < subarraySize; i++) {
freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);
if (freq.get(nums[i]) > k) return false;
}
for (int i = subarraySize; i < nums.length; i++) {
freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);
if (freq.get(nums[i]) > k) return false;
freq.put(nums[i - subarraySize], freq.get(nums[i - subarraySize]) - 1);
if (freq.get(nums[i - subarraySize]) == 0) {
freq.remove(nums[i - subarraySize]);
}
}
return true;
}
public static int longestGoodSubarray(int[] nums, int k) {
int low = 1, high = nums.length, answer = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (isGoodSubarray(nums, mid, k)) {
answer = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 1, 2, 3, 1, 2};
int k = 2;
System.out.println(longestGoodSubarray(nums, k));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
bool isGoodSubarray(vector<int>& nums, int subarraySize, int k) {
unordered_map<int, int> freq;
for (int i = 0; i < subarraySize; i++) {
freq[nums[i]]++;
if (freq[nums[i]] > k) return false;
}
for (int i = subarraySize; i < nums.size(); i++) {
freq[nums[i]]++;
if (freq[nums[i]] > k) return false;
freq[nums[i - subarraySize]]--;
if (freq[nums[i - subarraySize]] == 0) {
freq.erase(nums[i - subarraySize]);
}
}
return true;
}
int longestGoodSubarray(vector<int>& nums, int k) {
int low = 1, high = nums.size(), answer = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (isGoodSubarray(nums, mid, k)) {
answer = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
int main() {
vector<int> nums = {1, 2, 3, 1, 2, 3, 1, 2};
int k = 2;
cout << longestGoodSubarray(nums, k) << endl;
return 0;
}function isGoodSubarray(nums, subarraySize, k) {
let freq = new Map();
for (let i = 0; i < subarraySize; i++) {
freq.set(nums[i], (freq.get(nums[i]) || 0) + 1);
if (freq.get(nums[i]) > k) return false;
}
for (let i = subarraySize; i < nums.length; i++) {
freq.set(nums[i], (freq.get(nums[i]) || 0) + 1);
if (freq.get(nums[i]) > k) return false;
freq.set(nums[i - subarraySize], freq.get(nums[i - subarraySize]) - 1);
if (freq.get(nums[i - subarraySize]) === 0) {
freq.delete(nums[i - subarraySize]);
}
}
return true;
}
function longestGoodSubarray(nums, k) {
let low = 1, high = nums.length, answer = 0;
while (low <= high) {
let mid = Math.floor(low + (high - low) / 2);
if (isGoodSubarray(nums, mid, k)) {
answer = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
const nums = [1, 2, 3, 1, 2, 3, 1, 2];
const k = 2;
console.log(longestGoodSubarray(nums, k));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
bool isGoodSubarray(int* nums, int numsSize, int subarraySize, int k) {
int* frequency = (int*)calloc(1000000001, sizeof(int));
int distinct = 0;
for (int i = 0; i < subarraySize; i++) {
frequency[nums[i]]++;
}
for (int i = 0; i < numsSize; i++) {
if (i >= subarraySize) {
frequency[nums[i - subarraySize]]--;
}
if (frequency[nums[i]] > k) {
free(frequency);
return false;
}
}
free(frequency);
return true;
}
int longestGoodSubarray(int* nums, int numsSize, int k) {
int low = 1, high = numsSize, answer = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (isGoodSubarray(nums, numsSize, mid, k)) {
answer = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
int main() {
int nums[] = {1, 2, 3, 1, 2, 3, 1, 2};
int k = 2;
printf("%d\n", longestGoodSubarray(nums, 8, k));
return 0;
}using System;
using System.Collections.Generic;
class Program {
public static bool IsGoodSubarray(int[] nums, int subarraySize, int k) {
Dictionary<int, int> freq = new Dictionary<int, int>();
for (int i = 0; i < subarraySize; i++) {
if (!freq.ContainsKey(nums[i])) freq[nums[i]] = 0;
freq[nums[i]]++;
if (freq[nums[i]] > k) return false;
}
for (int i = subarraySize; i < nums.Length; i++) {
if (!freq.ContainsKey(nums[i])) freq[nums[i]] = 0;
freq[nums[i]]++;
if (freq[nums[i]] > k) return false;
freq[nums[i - subarraySize]]--;
if (freq[nums[i - subarraySize]] == 0) freq.Remove(nums[i - subarraySize]);
}
return true;
}
public static int LongestGoodSubarray(int[] nums, int k) {
int low = 1, high = nums.Length, answer = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (IsGoodSubarray(nums, mid, k)) {
answer = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
static void Main() {
int[] nums = {1, 2, 3, 1, 2, 3, 1, 2};
int k = 2;
Console.WriteLine(LongestGoodSubarray(nums, k));
}
}In Python, the function employs binary search to explore the potential maximum subarray length. For each candidate length, the validity of the subarray is determined by a helper function that reviews the current sliding window setup using defaultdict for frequencies.
Time Complexity: O(n log n).
Space Complexity: O(n) employing a dictionary for frequency counts.
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.
function maxSubarrayLength(nums: number[], k: number): number {
const cnt: Map<number, number> = new Map();
let ans = 0;
for (let i = 0, j = 0; i < nums.length; ++i) {
cnt.set(nums[i], (cnt.get(nums[i]) ?? 0) + 1);
for (; cnt.get(nums[i])! > k; ++j) {
cnt.set(nums[j], cnt.get(nums[j])! - 1);
}
ans = Math.max(ans, i - j + 1);
}
return ans;
}func maxSubarrayLength(nums []int, k int) (ans int) {
cnt := map[int]int{}
for i, j, n := 0, 0, len(nums); i < n; i++ {
cnt[nums[i]]++
for ; cnt[nums[i]] > k; j++ {
cnt[nums[j]]--
}
ans = max(ans, i-j+1)
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window with Frequency Map | Time Complexity: |
| Binary Search Over Subarray Length | Time Complexity: |
| Two Pointers | – |
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 |
Frequently asked questions
Is Length of Longest Subarray With at Most K Frequency easy or hard?
The problem is classified as Medium difficulty. The challenge is recognizing that the constraint can be maintained with a sliding window and frequency map. Once the pattern is identified, the implementation is straightforward and linear time.
Length of Longest Subarray With at Most K Frequency Python/Java solution
Python solutions typically use a dictionary or collections.Counter for frequency tracking, while Java implementations use HashMap<Integer, Integer>. Both implementations follow the same sliding window pattern with two pointers and run in O(n) time.
How to solve Length of Longest Subarray With at Most K Frequency in O(n)?
Use a sliding window and maintain a hash map that stores the frequency of elements in the current window. Expand the right pointer and update the frequency. If any element appears more than k times, move the left pointer and decrement counts until the window becomes valid. Track the maximum window length during the process.
What is the best approach for Length of Longest Subarray With at Most K Frequency?
The optimal approach uses a sliding window with a frequency hash map. Two pointers track the current window while a map stores how many times each value appears. When any frequency exceeds k, move the left pointer forward until the window becomes valid again. This solution runs in O(n) time with O(n) space.
Is Length of Longest Subarray With at Most K Frequency asked at Google/Amazon/Meta?
Problems involving sliding window frequency constraints frequently appear in interviews at companies like Amazon, Google, and Meta. Variants include longest substring with limited repeats or subarrays with frequency constraints. Interviewers use them to test window management and hash map usage.
What data structure is used in Length of Longest Subarray With at Most K Frequency?
The core data structure is a hash table (or dictionary) that stores the frequency of each element in the current window. Combined with two pointers for the sliding window, it allows constant‑time updates and checks while scanning the array.
What is the time complexity of Length of Longest Subarray With at Most K Frequency?
The optimal sliding window solution runs in O(n) time because each element enters and leaves the window at most once. Frequency updates and lookups in the hash map are O(1) on average. The auxiliary space is O(n) in the worst case if all elements are distinct.