Length of Longest Subarray With at Most K Frequency

You are given an integer array nums and an integer k. 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:

• nums = [1,2,3,1,2,3,1,2], k = 2. The longest good subarray is [1,2,3,1,2,3] with a length of 6.
• nums = [1,2,1,2,1,2,1,2], k = 1. The longest good subarray is [1,2] with a length of 2.
• nums = [5,5,5,5,5,5,5], k = 4. The longest good subarray is [5,5,5,5] with a length of 4.

Write an algorithm to efficiently determine the length of the longest good subarray given the array nums and the integer k.

## Naive Solution

The naive solution would be to iterate through all possible subarrays and, for each subarray, check if it is a "good" subarray according to the problem description. This involves counting the frequency of each element within the subarray and ensuring that no element's frequency exceeds `k`. If a subarray is found to be good, we compare its length with the current maximum length and update the maximum length accordingly.

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

Optimal Solution (Sliding Window)

We can use a sliding window approach to solve this problem more efficiently. We maintain a window and a frequency map of the elements within the window. We expand the window to the right until we find an element whose frequency exceeds k. When this happens, we shrink the window from the left until all element frequencies are at most k again. During the process, we keep track of the maximum length of a good subarray.

def longest_good_subarray(nums, k):
    max_len = 0
    left = 0
    counts = {}

    for right in range(len(nums)):
        counts[nums[right]] = counts.get(nums[right], 0) + 1

        while counts[nums[right]] > k:
            counts[nums[left]] -= 1
            if counts[nums[left]] == 0:
                del counts[nums[left]]
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len

Example

Let's consider nums = [1, 2, 3, 1, 2, 3, 1, 2] and k = 2.

1. We start with an empty window (left = 0, right = 0).
2. We expand the window to the right, adding elements to our counts map:
   • right = 0: nums[0] = 1, counts = {1: 1}
   • right = 1: nums[1] = 2, counts = {1: 1, 2: 1}
   • right = 2: nums[2] = 3, counts = {1: 1, 2: 1, 3: 1}
   • right = 3: nums[3] = 1, counts = {1: 2, 2: 1, 3: 1}
   • right = 4: nums[4] = 2, counts = {1: 2, 2: 2, 3: 1}
   • right = 5: nums[5] = 3, counts = {1: 2, 2: 2, 3: 2}
   • right = 6: nums[6] = 1, counts = {1: 3, 2: 2, 3: 2}. Now counts[1] > k, so we shrink the window from the left.
   • We increment left, decreasing counts[nums[left]] at each step until counts[1] <= k.
   • left = 0: counts[1] = 3 - 1 = 2, left = 1
   • The window is now [2, 3, 1, 2, 3, 1]. max_len is updated.
3. The iterations continue in this fashion, the window sliding forward.

Big(O) Time Complexity Analysis

The optimal solution using the sliding window has a time complexity of O(n), where n is the length of the input array nums. In the worst-case scenario, we iterate through the array once with the right pointer and once with the left pointer. Although there is a while loop, each element is only visited a maximum of two times (once by the right pointer and potentially once by the left pointer), which ensures the linear time complexity.

The naive solution has a time complexity of O(n^3) because for each of the O(n^2) subarrays it costs O(n) to validate each subarray.

Big(O) Space Complexity Analysis

The space complexity of the optimal solution is O(u), where u is the number of unique elements in the input array nums. This is because we store the frequencies of the elements in a hash map counts. In the worst-case scenario, all elements in the array are unique, and the hash map will store all of them.

The naive solution has O(u) as well, for the frequency counts.

Edge Cases

1. Empty array: If the input array nums is empty, the function should return 0, since there are no subarrays.
2. k is zero: If k is zero, it means no element can appear more than zero times, so the longest good subarray can only contain unique elements and we need to find the longest such subarray.
3. All elements are the same: If all elements in the array are the same, the length of the longest good subarray will be k. For example, if nums = [5, 5, 5, 5, 5, 5, 5] and k = 4, the longest good subarray is [5, 5, 5, 5], and its length is 4.
4. k is greater than the array length: If k is greater than or equal to the length of the array, then the entire array is a good subarray, and the function should return the length of the array.
5. Large input: Need to ensure the solution handles arrays of 10^5 elements without exceeding time limits. The sliding window approach is optimal here.