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:

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.

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.

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.

What is the most efficient algorithm (time and space complexity) to solve this problem?

## Naive Approach

A brute-force approach would involve checking all possible subarrays of `nums` to see if they are "good" (i.e., each element's frequency is less than or equal to `k`). For each subarray, we'd count the frequency of each element and verify the condition.

### Code (Python)

```python
def is_good(subarray, k):
    freq = {}
    for num in subarray:
        freq[num] = freq.get(num, 0) + 1
        if freq[num] > k:
            return False
    return True


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]
            if is_good(subarray, k):
                max_len = max(max_len, len(subarray))
    return max_len

# Example usage
nums = [1, 2, 3, 1, 2, 3, 1, 2]
k = 2
print(longest_good_subarray_naive(nums, k))  # Output: 6

Big O Run-time Analysis

• The outer loop iterates n times.
• The inner loop iterates up to n times.
• The is_good function iterates through the subarray, which can be up to length n.
• Overall: O(n^3)

Big O Space Usage Analysis

• The is_good function uses a dictionary to store frequencies, which can grow up to the size of the subarray (up to n).
• Overall: O(n)

Optimal Solution: Sliding Window

A more efficient approach is to use the sliding window technique. We maintain a window and a frequency map. As we expand the window, we update the frequency map. If at any point an element's frequency exceeds k, we shrink the window from the left until the condition is satisfied.

Code (Python)

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

    for right in range(len(nums)):
        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

# Example usage
nums = [1, 2, 3, 1, 2, 3, 1, 2]
k = 2
print(longest_good_subarray(nums, k))  # Output: 6

Big O Run-time Analysis

• The outer loop iterates n times.
• The inner while loop may iterate multiple times in one outer loop iteration, but on average, each element is visited a constant number of times.
• Overall: O(n)

Big O Space Usage Analysis

• The frequency map stores the frequency of elements in the current window, which can grow up to n in the worst case.
• Overall: O(n)

Edge Cases

1. Empty array: If the input array nums is empty, the function should return 0.
2. k = 0: If k is 0, the function should return 0 because no element can have a frequency greater than 0.
3. All elements are the same: If all elements in the array are the same, the function should return the minimum of the array length and k.

These edge cases are handled correctly by the sliding window algorithm. The initial values are correctly set up and it handles an empty frequency map gracefully during shrinking of the window.