Length of Longest Subarray With at Most K Frequency

Medium
800.

Length of Longest Subarray With at Most K Frequency

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.

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 <= 100000
  • 1 <= nums[i] <= 1000000000
  • 1 <= k <= nums.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxSubarrayLength = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 100000
  • 1 <= nums[i] <= 1000000000
  • 1 <= k <= nums.length

Hints for Length of Longest Subarray With at Most K Frequency

  1. Hint 1

    Removing elements can only lower every frequency, so 'good' is monotone in the left edge.

  2. Hint 2

    Only the value just added can break the invariant — no need to scan every frequency.

  3. 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

  1. Add nums[r] to the tally.
  2. While its count exceeds k, remove nums[l] from the tally and advance l.
  3. 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 best

Java

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