2958. Length of Longest Subarray With at Most K Frequency

Problem Description

You are given an array of integers, nums, and another integer, k. The term "frequency" refers to how often an element occurs in the array. A "good" array is defined as an array where each element's frequency is no more than k. The main objective is to find the length of the longest subarray within nums that qualifies as "good". Remember, a subarray is a consecutive sequence that forms part of the larger array.

Intuition

To find the longest "good" subarray, we can use a sliding window approach. The "window" in this context is a range of consecutive items in nums, which we will continuously adjust to find the longest range that meets our frequency criteria.

Here's how we think through it:

1. First, understand that a subarray is "good" when none of its elements occur more than k times.
2. We will have two pointers, representing the start and end of the subarray, moving through nums. These pointers define our current window.
3. We grow the window by moving the end pointer forward and track the frequency of each element in the window.
4. If the frequency of the new element pushes it over k, the subarray isn't "good" anymore. We then need to shrink the window from the start until we remove enough instances of any over-represented element to make the subarray "good" again.
5. As we shift our window, we'll remember the size of the largest "good" subarray we've seen so far. This is our answer.

The key insight is realizing that we can dynamically adjust our window to find the optimal size. By using a hash map to count element frequencies and a while loop to maintain the "good" criteria, we ensure our solution is efficient and doesn't re-scan parts of the array unnecessarily.

Learn more about Sliding Window patterns.

Solution Approach

The implementation of the solution uses the two-pointer technique combined with a hash map to achieve an efficient way of finding the longest "good" subarray. Here's a detailed walkthrough aligned with the code provided:

1. We start by initializing a defaultdict(int) named cnt to keep track of the frequency of each element in our current window.

2. We then set ans to 0, which will eventually hold the length of the longest "good" subarray found. Also, we initialize a pointer j to 0, which represents the start of the current subarray (the sliding window's left edge).

3. The for loop begins by iterating over each element x in the list nums, with i denoting the current position (forming the sliding window's right edge).

4. For each element x, the code cnt[x] += 1 increments its frequency in the hash map.

5. Now we check if the subarray [j, i] is not "good" anymore by seeing if the frequency of x exceeds k. The while loop while cnt[x] > k: is activated if the condition is true.

6. Inside the loop, we move j to the right (j += 1) to shrink the window, decrementing the frequency of nums[j] in cnt to reflect this change. This process repeats until the frequency of x is k or less, making the current window "good" again.

7. After each iteration and making sure the window is "good", the length of the current subarray (i - j + 1) is compared with the maximum length found so far (ans), and ans is updated if the current length is greater. This is done using ans = max(ans, i - j + 1).

8. Once we've checked all elements, the for loop ends, and we return ans, which now holds the longest length of a "good" subarray.

This algorithm efficiently compromises between expanding and shrinking the window to account for every possible "good" subarray, using the cnt hash map to keep track of frequencies and two pointers to keep track of the window's bounds. By updating ans each time we find a longer "good" subarray, we ensure the final answer holds the maximum length required.

Example Walkthrough

Let's consider a small example to illustrate the solution approach:

Suppose we are given an array of integers nums = [1, 2, 2, 3, 1, 2, 3] and another integer k = 2. We are tasked with finding the length of the longest subarray where no element appears more than k times.

Following our solution approach:

1. We start with initializing our hash map cnt to keep track of the frequencies, a variable ans set to 0 to track the length of the longest "good" subarray, and a pointer j initialized to 0 for the start position of our window.

2. Next, we begin iterating over nums from left to right:

   • At i = 0, nums[i] = 1. We increment cnt[1] to 1 and since all frequencies are within k, we update ans to 1.

   • At i = 1, nums[i] = 2. We increment cnt[2] to 1. The subarray [1, 2] is "good" and ans is updated to 2.

   • At i = 2, nums[i] = 2. We increment cnt[2] to 2. The subarray [1, 2, 2] is still "good", so ans becomes 3.

   • At i = 3, nums[i] = 3. cnt[3] becomes 1, and the subarray [1, 2, 2, 3] is "good". Update ans to 4.

   • At i = 4, nums[i] = 1. The frequency of 1 is now 2, and the subarray [1, 2, 2, 3, 1] is "good", so ans is now 5.

   • At i = 5, nums[i] = 2. Now cnt[2] becomes 3, which is over k. To restore the "good" status, we shift j rightward. First, we decrement cnt[1] by 1 as we move past the first element, but cnt[2] is still 3, so we shift j again, decrementing cnt[2] by 1. Now cnt[2] is 2, the subarray [2, 2, 3, 1, 2] is "good", and ans remains at 5.

   • At i = 6, nums[i] = 3. Again, the subarray [2, 2, 3, 1, 2, 3] is "good" and ans is updated to 6, which is the length of this "good" subarray.

3. Since we have gone through all elements, our final answer ans is 6, the length of the longest "good" subarray [2, 2, 3, 1, 2, 3].

This example clearly demonstrates how we use the two-pointer technique in tandem with the frequency hash map to efficiently determine the longest "good" subarray in nums.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n). This is because the function has a single loop iterating through the elements of nums from start to end, performing a fixed set of operations for each element. Therefore, the time taken by the function scales linearly with the size of the input list nums.

Space Complexity

The space complexity of the code is O(n). This arises due to the use of the cnt dictionary that stores the count of elements. In the worst case, where all elements in nums are unique, the dictionary would contain an entry for each distinct element, leading to a space requirement that scales linearly with the size of the input list nums.

Learn more about how to find time and space complexity quickly using problem constraints.