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.

Example 1: nums = [1,2,3,1,2,3,1,2], k = 2. The output should be 6 because [1,2,3,1,2,3] is the longest good subarray since the values 1, 2, and 3 occur at most twice in this subarray.

Example 2: nums = [1,2,1,2,1,2,1,2], k = 1. The output should be 2 because [1,2] is the longest possible good subarray since the values 1 and 2 occur at most once in this subarray.

Example 3: nums = [5,5,5,5,5,5,5], k = 4. The output should be 4 because [5,5,5,5] is the longest possible good subarray since the value 5 occurs 4 times in this subarray.

Write an algorithm to efficiently solve the problem, considering that 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^9, and 1 <= k <= nums.length.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// Naive Solution (Brute Force)
// Time Complexity: O(n^3)
// Space Complexity: O(n)
int longestGoodSubarrayNaive(const vector<int>& nums, int k) {
    int maxLen = 0;
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = i; j < nums.size(); ++j) {
            unordered_map<int, int> freq;
            bool good = true;
            for (int l = i; l <= j; ++l) {
                freq[nums[l]]++;
                if (freq[nums[l]] > k) {
                    good = false;
                    break;
                }
            }
            if (good) {
                maxLen = max(maxLen, j - i + 1);
            }
        }
    }
    return maxLen;
}

// Optimal Solution (Sliding Window)
// Time Complexity: O(n)
// Space Complexity: O(n)
int longestGoodSubarrayOptimal(const vector<int>& nums, int k) {
    int maxLen = 0;
    int left = 0;
    unordered_map<int, int> freq;

    for (int right = 0; right < nums.size(); ++right) {
        freq[nums[right]]++;

        while (freq[nums[right]] > k) {
            freq[nums[left]]--;
            left++;
        }

        maxLen = max(maxLen, right - left + 1);
    }

    return maxLen;
}

int main() {
    vector<int> nums1 = {1, 2, 3, 1, 2, 3, 1, 2};
    int k1 = 2;
    cout << "Example 1: " << longestGoodSubarrayOptimal(nums1, k1) << endl; // Output: 6

    vector<int> nums2 = {1, 2, 1, 2, 1, 2, 1, 2};
    int k2 = 1;
    cout << "Example 2: " << longestGoodSubarrayOptimal(nums2, k2) << endl; // Output: 2

    vector<int> nums3 = {5, 5, 5, 5, 5, 5, 5};
    int k3 = 4;
    cout << "Example 3: " << longestGoodSubarrayOptimal(nums3, k3) << endl; // Output: 4

    return 0;
}

Naive Solution

The naive solution iterates through all possible subarrays and checks if each subarray is good. For each subarray, it counts the frequency of each element and checks if the frequency is less than or equal to k. If it is, the length of the subarray is compared with the maximum length found so far.

Optimal Solution

The optimal solution uses the sliding window technique. We maintain a window and a frequency map of the elements within the window. We expand the window to the right, and if the frequency of an element exceeds k, we shrink the window from the left until the frequency is no longer greater than k. At each step, we update the maximum length of the good subarray.

Big(O) Run-time Analysis

Naive Solution:

• The outer loop iterates n times.
• The inner loop iterates up to n times.
• The frequency counting loop iterates up to n times.
• Therefore, the time complexity is O(n^3).

Optimal Solution:

• The outer loop iterates n times.
• The inner while loop (shrinking the window) in the worst case iterates n times in total across all iterations of the outer loop.
• Therefore, the time complexity is O(n).

Big(O) Space Usage Analysis

Naive Solution:

• The freq map stores the frequencies of elements in the current subarray.
• In the worst case, the subarray can contain n distinct elements.
• Therefore, the space complexity is O(n).

Optimal Solution:

• The freq map stores the frequencies of elements in the current window.
• In the worst case, the window can contain n distinct elements.
• Therefore, the space complexity is O(n).

Edge Cases

1. Empty Array: If the input array is empty, the longest good subarray length is 0.
2. k = 0: If k is 0, then any subarray with repeating elements is not good. The longest good subarray would consist of only unique elements.
3. k >= n: If k is greater than or equal to the length of the array, the entire array is a good subarray, so the length of the array is the answer.
4. All elements are the same: If all elements in the array are the same, the longest good subarray would be of length k (or the array length if it's less than k).