Length of Longest Subarray With at Most K Frequency

medium sliding window hash table two pointers

Problem

Given an integer array nums and an integer k, a subarray is good if every value inside it occurs at most k times. Return the length of the longest good subarray. A subarray is a contiguous, non-empty slice of nums.

Inputnums = [1,2,3,1,2,3,1,2], k = 2

Output6

The window [1,2,3,1,2,3] is good: 1, 2, 3 each appear at most twice. Extending it to the next 1 would make three 1's, so 6 is the longest.

nums (comma-separated)

def maxSubarrayLength(nums, k):
    freq = {}                       # value -> count inside the window
    left = 0
    best = 0
    for right in range(len(nums)):
        x = nums[right]
        freq[x] = freq.get(x, 0) + 1
        while freq[x] > k:          # x now appears too often
            freq[nums[left]] -= 1   # shrink from the left
            left += 1
        best = max(best, right - left + 1)
    return best

function maxSubarrayLength(nums, k) {
  const freq = new Map();           // value -> count inside the window
  let left = 0, best = 0;
  for (let right = 0; right < nums.length; right++) {
    const x = nums[right];
    freq.set(x, (freq.get(x) || 0) + 1);
    while (freq.get(x) > k) {        // x now appears too often
      freq.set(nums[left], freq.get(nums[left]) - 1);
      left++;                        // shrink from the left
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

int maxSubarrayLength(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    int left = 0, best = 0;
    for (int right = 0; right < nums.length; right++) {
        int x = nums[right];
        freq.merge(x, 1, Integer::sum);     // count inside window
        while (freq.get(x) > k) {           // x appears too often
            freq.merge(nums[left], -1, Integer::sum);
            left++;                          // shrink from the left
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

int maxSubarrayLength(vector<int>& nums, int k) {
    unordered_map<int, int> freq;       // value -> count in window
    int left = 0, best = 0;
    for (int right = 0; right < (int)nums.size(); right++) {
        int x = nums[right];
        freq[x]++;
        while (freq[x] > k) {            // x appears too often
            freq[nums[left]]--;          // shrink from the left
            left++;
        }
        best = max(best, right - left + 1);
    }
    return best;
}

Explanation

We keep a sliding window [left, right] that is always good — every value inside it appears at most k times — and we track the largest length such a window ever reaches.

A hash map freq stores how many times each value currently sits inside the window. As right sweeps left to right, we add nums[right] and bump its count.

Adding that element can only push one value over the limit: the value we just inserted, x = nums[right]. So whenever freq[x] > k, we advance left, decrementing the count of each value we drop, until x is back to k occurrences and the window is good again.

After repairing the window we record best = max(best, right - left + 1). Because left never moves backward, every index enters and leaves the window at most once, giving a single linear pass.

For nums = [1,2,3,1,2,3,1,2], k = 2 the window grows to [1,2,3,1,2,3] (length 6). The next 1 would be a third 1, so left slides forward; the window length never exceeds 6, which is the answer.

Time: O(n) Space: O(n)