Get started

Length of Longest Subarray With at Most K Frequency — Medium Problem & Solution

A subarray is good when every value in it appears at most k times. Return the length of the longest good subarray of nums.

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

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue