Length of Longest Subarray With at Most K Frequency

Problem Statement

In this problem, we're provided with an integer array nums and an integer k. The objective is to identify the longest contiguous subarray of nums such that the frequency of each element within that subarray does not exceed k, where the frequency is defined as the number of occurrences of an element within the array. We need to return the length of this longest "good" subarray. A subarray is a contiguous part of the original array and all elements must satisfy the frequency condition to qualify as "good".

Examples

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 <= 105
• 1 <= nums[i] <= 109
• 1 <= k <= nums.length

Approach and Intuition

To solve this problem efficiently, the concept of a sliding window combined with a frequency map can be effectively applied. Here's a step-by-step plan:

1. Initialize two pointers to represent the current window of the array. These are usually termed as the start and end pointers.
2. Use a hashmap (or dictionary) to keep track of the frequency of each element within the current window.
3. Expand the end pointer to include elements in the window until the condition is violated (i.e., the frequency of some element in the window exceeds k).
4. Once the condition is violated, start moving the start pointer to the right to reduce the size of the window until the subarray becomes "good" again (i.e., the frequency of all elements are within the limit set by k).
5. The size of the window at each valid state (where all frequencies are ≤ k) can be considered as a potential answer. Always update and record the maximum size obtained.
6. Continue this until the end pointer has traversed the entire array.

• Example walkthrough with nums = [1,2,3,1,2,3,1,2], k = 2:
  • Increase the window size by moving end until you exceed k with any number.
  • Initially, the window grows to encompass 1,2,3,1,2,3 before any frequency exceeds k.
  • At this point, the largest good window has a length of 6.
  • Adjust start and end trying to find a potentially larger good subarray, but none can be found in this instance.

This approach ensures that each element is processed a limited number of times, making the sliding window technique efficient for this problem. The use of the frequency hashmap enables quick checks and updates for the conditions described.

Solutions

class Solution {
public:
    int longestUniformSubarray(vector<int>& elements, int threshold) {
        int len = elements.size(); 
        unordered_map<int, int> countMap; 
        int left = 0;
        int excessCount = 0;
            
        for (int right = 0; right < len; right++) {
            countMap[elements[right]]++;
            if (countMap[elements[right]] == threshold + 1) {
                excessCount++;
            }
            if (excessCount > 0) {
                countMap[elements[left]]--;
                if (countMap[elements[left]] == threshold) {
                    excessCount--;
                }
                left++;
            }
        }
        return len - left;
    }
};