Length of Longest Subarray With at Most K Frequency

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. For example:

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 <= 10^5 1 <= nums[i] <= 10^9 1 <= k <= nums.length

## Naive Solution

The brute-force solution involves iterating through all possible subarrays and checking if each subarray is "good" according to the given definition. For each subarray, we count the frequency of each element and verify if the frequency of every element is less than or equal to `k`. The longest such subarray is then recorded.

```python
def longest_good_subarray_naive(nums, k):
    n = len(nums)
    max_len = 0
    for i in range(n):
        for j in range(i, n):
            subarray = nums[i:j+1]
            freq = {}
            is_good = True
            for num in subarray:
                freq[num] = freq.get(num, 0) + 1
                if freq[num] > k:
                    is_good = False
                    break
            if is_good:
                max_len = max(max_len, len(subarray))
    return max_len

Time Complexity: O(n^3)

• We have nested loops that iterate through all possible subarrays, which takes O(n^2) time.
• For each subarray, we iterate through it to count the frequencies of elements, which takes O(n) time in the worst case.
• Therefore, the overall time complexity is O(n^2 * n) = O(n^3).

Space Complexity: O(n)

• In the worst case, the freq dictionary can store all unique elements in the subarray, which can be up to O(n) in size.

Optimal Solution

The optimal solution uses a sliding window approach. We maintain a window and track the frequencies of elements within the window. We expand the window to the right until we find an element whose frequency exceeds k. Then, we shrink the window from the left until all element frequencies are less than or equal to k again. We keep track of the maximum window size that satisfies the condition.

def longest_good_subarray_optimal(nums, k):
    n = len(nums)
    freq = {}
    left = 0
    max_len = 0
    
    for right in range(n):
        freq[nums[right]] = freq.get(nums[right], 0) + 1
        
        while freq[nums[right]] > k:
            freq[nums[left]] -= 1
            if freq[nums[left]] == 0:
                del freq[nums[left]]
            left += 1
            
        max_len = max(max_len, right - left + 1)
        
    return max_len

Time Complexity: O(n)

• We iterate through the array once with the right pointer. The left pointer also moves from left to right, but it does not iterate through the array independently. Thus, each element is visited at most twice (once by right and once by left).
• The operations within the loop (dictionary updates and comparisons) take constant time.
• Therefore, the overall time complexity is O(n).

Space Complexity: O(n)

• In the worst case, the freq dictionary can store the frequencies of all unique elements in the input array, which can be up to O(n) in size.

Edge Cases

1. Empty Array: If the input array nums is empty, the function should return 0 because there are no subarrays.
2. k = 0: If k is 0, the longest good subarray will have a length of 0 because no element can appear even once.
3. k >= n: If k is greater than or equal to the length of the array n, then the entire array is a good subarray, so the function should return n.
4. All elements are the same: Consider an array like [5, 5, 5, 5, 5] and k = 2. The correct output should be 2.
5. Array with distinct elements: Consider an array like [1, 2, 3, 4, 5] and k = 1. The correct output should be 1 since each element can appear at most once in the subarray.

These edge cases are handled correctly by the optimal solution provided above.