# Length of Longest Subarray With at Most K Frequency
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/length-of-longest-subarray-with-at-most-k-frequency)
Canonical: https://scaleengineer.com/dsa/problems/length-of-longest-subarray-with-at-most-k-frequency
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array, Hash Table
**Companies:** [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Citadel](https://scaleengineer.com/companies/citadel)
---
## Problem
You are given an integer array `nums` and an integer `k`.

The **frequency** of an element `x` is the number of times it occurs in an array.

An array is called **good** if the frequency of each element in this array is **less than or equal** to `k`.

Return _the length of the **longest** **good** subarray of_ `nums`_._

A **subarray** is a contiguous non-empty sequence of elements within an array.

**Example 1:**

**Input:** nums = [1,2,3,1,2,3,1,2], k = 2
**Output:** 6
**Explanation:** The longest possible good subarray is [1,2,3,1,2,3] since the values 1, 2, and 3 occur at most twice in this subarray. Note that the subarrays [2,3,1,2,3,1] and [3,1,2,3,1,2] are also good.
It can be shown that there are no good subarrays with length more than 6.

**Example 2:**

**Input:** nums = [1,2,1,2,1,2,1,2], k = 1
**Output:** 2
**Explanation:** The longest possible good subarray is [1,2] since the values 1 and 2 occur at most once in this subarray. Note that the subarray [2,1] is also good.
It can be shown that there are no good subarrays with length more than 2.

**Example 3:**

**Input:** nums = [5,5,5,5,5,5,5], k = 4
**Output:** 4
**Explanation:** The longest possible good subarray is [5,5,5,5] since the value 5 occurs 4 times in this subarray.
It can be shown that there are no good subarrays with length more than 4.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`
* `1 <= k <= nums.length`

# Approaches
## Brute Force with Optimization
This approach involves checking every possible subarray to see if it's a "good" subarray. A good subarray is one where the frequency of each element is at most `k`. We iterate through all possible start points of a subarray and, for each start point, extend the subarray to the right, checking its validity at each step.
**Time:** O(N^2), where N is the number of elements in `nums`. The two nested loops lead to a quadratic number of operations. For each pair of `(i, j)`, the operations inside the inner loop are constant time on average (for HashMap). · **Space:** O(U) or O(N) in the worst case, where U is the number of unique elements in the subarray `nums[i...j]`. In the worst case, all elements are unique, so the space required for the `frequencyMap` can be up to O(N).
**Pros:** Simple to understand and implement.; It's a direct translation of the problem statement.
**Cons:** Inefficient for large inputs due to its quadratic time complexity.; It will likely result in a "Time Limit Exceeded" (TLE) error on platforms with large test cases.; Redundant computations: The frequency map is rebuilt for each starting position `i`, recalculating frequencies for overlapping parts of subarrays.
### Explanation
We use two nested loops to generate all subarrays. The outer loop, with index `i`, determines the starting point of the subarray. The inner loop, with index `j`, determines the ending point.

For each starting point `i`, we initialize a frequency map. As we extend the subarray by incrementing `j`, we update the frequency of the new element `nums[j]` in the map.

After updating, we check if the frequency of `nums[j]` exceeds `k`.

If it does, the current subarray `nums[i...j]` is not good. Since any further extension of this subarray (by increasing `j`) will also include this violation, it will also not be good. Therefore, we can break the inner loop and move to the next starting point `i+1`.

If the frequency does not exceed `k`, the subarray `nums[i...j]` is good. We then update our maximum length found so far with the length of this current subarray, which is `j - i + 1`.

This process is repeated for all possible starting positions.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        int n = nums.length;
        int maxLength = 0;

        if (n == 0) {
            return 0;
        }

        for (int i = 0; i < n; i++) {
            Map<Integer, Integer> frequencyMap = new HashMap<>();
            for (int j = i; j < n; j++) {
                int currentNum = nums[j];
                frequencyMap.put(currentNum, frequencyMap.getOrDefault(currentNum, 0) + 1);

                if (frequencyMap.get(currentNum) > k) {
                    break; // This subarray and any longer ones starting at i are invalid
                }
                maxLength = Math.max(maxLength, j - i + 1);
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 0`.
- Iterate through the array with an index `i` from `0` to `n-1` to select the start of the subarray.
- For each `i`, create a new frequency map.
- Iterate with an index `j` from `i` to `n-1` to select the end of the subarray.
- In the inner loop, add `nums[j]` to the current subarray and update its frequency in the map.
- Check if the frequency of `nums[j]` is greater than `k`.
- If it is, the subarray `nums[i...j]` is invalid. Break the inner loop and try the next starting position `i+1`.
- If it's not, the subarray is valid. Update `maxLength = max(maxLength, j - i + 1)`.
- After all subarrays are checked, return `maxLength`.

## Optimal Sliding Window
This approach uses a sliding window, defined by two pointers `start` and `end`, to efficiently find the longest "good" subarray. We expand the window by moving the `end` pointer and shrink it by moving the `start` pointer whenever the subarray within the window becomes "bad" (i.e., an element's frequency exceeds `k`).
**Time:** O(N), where N is the number of elements in `nums`. Both the `start` and `end` pointers traverse the array at most once, so each element is visited a constant number of times. · **Space:** O(U) or O(N) in the worst case, where U is the number of unique elements in `nums`. The space is used for the `frequencyMap` to store the counts of elements in the current window.
**Pros:** Highly efficient with a linear time complexity.; Optimal solution for this problem, passing even for large inputs.; Processes each element a constant number of times.
**Cons:** Slightly more complex to reason about and implement compared to the brute-force approach.; Requires extra space for the frequency map.
### Explanation
We maintain a window `nums[start...end]` and a frequency map for the elements within this window.

We iterate through the array with the `end` pointer, from left to right, to expand the window.

In each step, we add `nums[end]` to our window and update its frequency in the map.

After adding `nums[end]`, we check if its frequency has exceeded `k`.

If `frequencyMap.get(nums[end]) > k`, the window is no longer "good". We must shrink the window from the left by incrementing the `start` pointer until the window becomes "good" again. This involves decrementing the frequency of `nums[start]` in our map and then moving `start` one position to the right. We repeat this shrinking process until the condition that caused the violation is resolved.

At each step, after ensuring the window `nums[start...end]` is "good", we calculate its length (`end - start + 1`) and update our `maxLength` if the current length is greater.

This way, both `start` and `end` pointers only move forward, ensuring each element is processed a constant number of times.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        int n = nums.length;
        int maxLength = 0;
        int start = 0;
        Map<Integer, Integer> frequencyMap = new HashMap<>();

        for (int end = 0; end < n; end++) {
            int endNum = nums[end];
            frequencyMap.put(endNum, frequencyMap.getOrDefault(endNum, 0) + 1);

            // Shrink the window from the left if the frequency of any element exceeds k
            while (frequencyMap.get(endNum) > k) {
                int startNum = nums[start];
                frequencyMap.put(startNum, frequencyMap.get(startNum) - 1);
                start++;
            }

            // Update the maximum length found so far
            maxLength = Math.max(maxLength, end - start + 1);
        }

        return maxLength;
    }
}
```
### Algorithm
- Initialize a `start` pointer to `0`, `maxLength` to `0`, and a frequency map.
- Iterate through the array with an `end` pointer from `0` to `n-1`.
- For each element `nums[end]`, increment its count in the frequency map.
- Check if the frequency of `nums[end]` has exceeded `k`.
- If it has, shrink the window from the left: repeatedly decrement the frequency of `nums[start]` and increment `start` until the window is valid again.
- After each potential expansion and necessary contraction, the window `nums[start...end]` is a valid "good" subarray. Update `maxLength` with the current window's size (`end - start + 1`).
- After the loop finishes, return `maxLength`.

# Solutions
### Java

```java
class Solution {
public
  int maxSubarrayLength(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    int ans = 0;
    for (int i = 0, j = 0; i < nums.length; ++i) {
      cnt.merge(nums[i], 1, Integer : : sum);
      while (cnt.get(nums[i]) > k) {
        cnt.merge(nums[j++], -1, Integer : : sum);
      }
      ans = Math.max(ans, i - j + 1);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxSubarrayLength(vector<int> &nums, int k) {
    unordered_map<int, int> cnt;
    int ans = 0;
    for (int i = 0, j = 0; i < nums.size(); ++i) {
      ++cnt[nums[i]];
      while (cnt[nums[i]] > k) {
        --cnt[nums[j++]];
      }
      ans = max(ans, i - j + 1);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int: cnt = defaultdict(int) ans = j = 0 for i, x in enumerate(nums): cnt[x] += 1 while cnt[x] > k: cnt[nums[j]] -= 1 j += 1 ans = max(ans, i - j + 1) return ans

```