DDSA Solutions

2958. Length of Longest Subarray With at Most K Frequency

MediumView on LeetCode
ArrayHash TableSliding Window

Problem Overview

A subarray is good when every value appears at most k times.

Intuition

A subarray is good when every value appears at most k times. As you grow a window, the only way it becomes bad is that the newly added value exceeds k - every other count was already legal. Shrink from the left until that value is back to k. Every window [l, r] you keep is good, so track the maximum length.

Algorithm

  1. 1Keep a frequency map for the current window [l, r] and ans = 0.
  2. 2For each right endpoint r: increment freq[nums[r]].
  3. 3While freq[nums[r]] > k: decrement freq[nums[l]] and advance l.
  4. 4Update ans with r - l + 1 (the current valid window length).
  5. 5Return ans. Leaving zero counts in the map is fine - unused keys do not affect correctness.

Example Walkthrough

Input: nums = [1, 2, 3, 1, 2, 3, 1, 2], k = 2

  1. 1.Grow to [1,2,3,1,2,3] - each of 1, 2, 3 appears twice; length 6.
  2. 2.Add the next 1 -> count(1) = 3 > 2. Shrink from the left until count(1) <= 2.
  3. 3.No later window is longer than 6, so the answer is 6.

Output: 6

Common Pitfalls

  • •You only need to shrink while the newly added value exceeds k - other values cannot suddenly break the limit.
  • •n can be 1e5, so O(n^2) nested scans will TLE; each index moves at most once.
  • •k can equal n; then the whole array is always good.
  • •Do not confuse "at most k frequency per value" with "at most k distinct values".
2958.cs
C#
// Approach: Sliding window. Expand r; track frequencies. When nums[r] appears
// more than k times, advance l until that count is <= k. Window length r-l+1
// is always valid; track the maximum. Skip removing zeroed keys - unused
// entries are harmless and saves dictionary churn.
// Complexity: O(n) time and O(min(n, U)) space (U = distinct values in the window).
public class Solution
{
    public int MaxSubarrayLength(int[] nums, int k)
    {
        var freq = new Dictionary<int, int>();
        int l = 0, ans = 0;

        for (int r = 0; r < nums.Length; r++)
        {
            freq.TryGetValue(nums[r], out int count);
            freq[nums[r]] = count + 1;

            while (freq[nums[r]] > k)
            {
                freq[nums[l]]--;
                l++;
            }

            ans = Math.Max(ans, r - l + 1);
        }

        return ans;
    }
}
Was this solution helpful?

Related Problems