Introduction

LeetCode 2958: Length of Longest Subarray With at Most K Frequency is an excellent problem to understand how sliding window with frequency counting works in arrays with duplicates.

The problem asks us to find the longest contiguous subarray such that no element occurs more than K times.

If you’d like to try solving the problem first, you can attempt it here:

Try the problem on LeetCode:

https://leetcode.com/problems/length-of-longest-subarray-with-at-most-k-frequency/

Problem Understanding

You are given:

1. An integer array nums
2. An integer k

A good subarray is defined as a subarray where the frequency of each element is ≤ k.

Goal: Return the length of the longest good subarray.

Examples:

A naive approach would check all subarrays and count frequencies →

1. Time Complexity: O(n²) → too slow for nums.length up to 10⁵

Key Idea: Sliding Window with Frequency Map

Instead of brute-force:

1. Use a sliding window [i, j] to track the current subarray
2. Use a HashMap mp to store the frequency of each element in the window
3. Expand j by adding nums[j] to the map
4. If mp.get(nums[j]) > k, shrink the window from the left (i) until mp.get(nums[j]) <= k
5. At each step, update the maximum length of the valid window

Intuition:

1. We allow each element to appear at most K times
2. By shrinking the window whenever a frequency exceeds k, we always maintain a valid subarray
3. Sliding window ensures linear traversal

Approach (Step-by-Step)

1. Initialize i = 0, j = 0 → window pointers
2. Initialize co = 0 → maximum length
3. Initialize HashMap mp to store frequencies of elements in the window
4. Iterate j from 0 to nums.length - 1:
5. Increment frequency of nums[j] in mp
6. While mp.get(nums[j]) > k:
7. Shrink window from the left by decrementing mp[nums[i]] and incrementing i
8. Update co = max(co, j - i + 1)
9. Return co as the length of the longest good subarray

Implementation (Java)

Dry Run Example

Input:

Execution:

Output:

Complexity Analysis

1. Time Complexity: O(n) → Each element enters and leaves the window at most once
2. Space Complexity: O(n) → HashMap stores frequencies of elements in the window (worst-case all distinct)

Edge Cases Considered

1. All elements occur ≤ k → entire array is valid
2. All elements occur > k → max subarray length = k
3. Single-element arrays → return 1 if k ≥ 1
4. Large arrays up to 10⁵ elements → O(n) solution works efficiently

Sliding Window Pattern Importance

This problem demonstrates sliding window with frequency map, useful for:

1. Subarrays with frequency constraints
2. Longest subarray with limited duplicates
3. Similar to "max consecutive ones with flips" and "fruit into baskets"

By mastering this approach, you can efficiently solve many array and subarray problems with constraints.

Conclusion

Using HashMap + sliding window, we reduce a naive O(n²) approach to O(n) while keeping the solution intuitive and easy to implement.

Understanding this pattern allows solving complex frequency-constrained subarray problems efficiently in interviews.