Longest Subarray with Every Value Occurring at Most k Times
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Longest Subarray with Every Value Occurring at Most k Times
You are given an integer array `nums` and an integer `k`. A subarray is good if every value in that subarray occurs at most `k` times.
Return the length of the longest good subarray. A subarray is a contiguous, nonempty sequence of elements.
### Examples
**Example 1**
```text
Input: nums = [4,1,4,2,4,2], k = 2
Output: 5
```
The suffix `[1,4,2,4,2]` has length `5` and contains each value at most twice. The only length-six subarray is the whole array, where `4` occurs three times, so no longer good subarray exists.
**Example 2**
```text
Input: nums = [2,3,4,3,5], k = 1
Output: 3
```
The subarrays `[2,3,4]` and `[4,3,5]` each have length `3` with no repeated value. Both length-four intervals, and the whole array, contain two occurrences of `3`, so no longer interval is good.
### Constraints
- `1 <= nums.length <= 10^5`.
- `1 <= nums[i] <= 10^9`.
- `1 <= k <= nums.length`.
### Clarifying Questions
- Is `k` a limit on the number of distinct values? No; it limits the frequency of each individual value.
- May a value occur exactly `k` times? Yes; the bound is inclusive.
- Can elements be skipped? No; the chosen subarray must be contiguous.
- Must the subarray itself be returned? No; return only its length.
- Can the answer be zero under these constraints? No; `k >= 1` and the array is nonempty, so every single-element subarray is good.
### C++ Interface
```cpp
class Solution {
public:
int maxSubarrayLength(vector<int>& nums, int k) {
}
};
```
### Reasoning Checkpoints
- Track frequencies within the current interval rather than across the whole array.
- Justify that the returned length is the largest among all good subarrays.
- Respect the nonempty subarray and inclusive per-value frequency limit.
```hint Repair the newly increased frequency
Extend a right endpoint and update its value's frequency. If that value exceeds k, move the left endpoint until the interval is good again. Which frequencies could have become invalid when just one element was appended?
```
Overview: Find the longest contiguous nonempty subarray in which each individual value occurs at most k times, returning only the maximum length.
