2831. Find the Longest Equal Subarray

MediumArrayHash TableBinary SearchSliding Window
Leetcode Link

Problem Description

In this problem, you're given an array of integers nums and an integer k. The task is to find the maximum length of a subarray where all elements are equal, after optionally deleting up to k elements from the array.

A subarray is defined as a contiguous part of the array which could be as small as an empty array or as large as the entire array. The concept of 'equality' here means that every item in the subarray is the same.

The challenge, therefore, is to figure out the strategy to remove up to k elements to maximize the length of this uniform subarray.

Intuition

The intuition behind the solution is to use a sliding window approach. The key insight is that the maximum length of equal subarray can be found by maintaining the count of elements within a given window and adjusting its size (using two pointers) to remove elements when necessary.

To implement this, iterate over the array while keeping track of the frequency of each element in the current window using a counter. The variable mx is used to keep track of the maximum frequency of any element that we've seen in our current window. This represents the largest potential equal subarray if we were to remove other elements.

We can have a window that exceeds this maximum frequency by k elements, as we're allowed to delete at most k elements. Whenever the size of our current window exceeds mx + k, this implies that we need to remove some elements to bring it back within the allowed size. We do this by shrinking the window from the left.

Iteration continues until we've processed all elements, and the length of the largest possible equal subarray is returned.

This approach works because it continually adjusts the window size to accommodate the highest frequency element while keeping count of the deletions within the limit of k. Whenever the limit is exceeded, the size of the window is reduced to restore the balance.

Learn more about Binary Search and Sliding Window patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is a min heap?

Solution Approach

The provided solution code employs a sliding window technique along with a counter to efficiently keep track of the number of occurrences of each element within the current window.

Here's a step-by-step analysis of the implementation:

  1. A counter named cnt is initialized using Counter from the collections module. This counter will keep track of the frequency of each element within the current window.
  2. Two pointers, l (left) and r (right), are used to define the boundaries of the sliding window. l starts at 0, and r is incremented in each iteration of the for loop.
  3. A variable mx, initialized at 0, is used to store the maximum frequency of any element within the current window throughout the iterations.
  4. The main loop iterates over the indices and values from the nums array. As r moves to the right, the corresponding value x in nums is added to the cnt counter.
  5. After each new element is added to cnt, the mx variable is updated to the maximum value between itself and the updated count for that element, effectively tracking the highest frequency element in the window.
  6. At any point, if the size of the current window (given by r - l + 1) minus the maximum frequency (mx) exceeds k, it indicates that we cannot delete enough elements to make the subarray equal. Thus, it's necessary to shrink the window from the left by incrementing l and decrementing the frequency of the lth element in cnt.
  7. This process continues until the end of the array is reached, ensuring that at each step, the window size exceeds mx + k by no more than one element.
  8. Finally, the length of the longest possible equal subarray (mx) that satisfies the condition after deleting at most k elements is returned.

This solution efficiently finds the longest equal subarray with a complexity of O(n), since it only requires a single pass over the input array, and operations within the loop are O(1) on average due to the use of the counter.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Example Walkthrough

Let's consider the array nums = [1, 1, 2, 2, 4, 4, 4, 2] and k = 2.

The aim is to find the maximum length of a subarray where all elements are equal after optionally deleting up to 2 elements.

Now, here's a step-by-step walkthrough using the sliding window approach:

  1. Initialize the counter cnt and pointers l = 0, r = 0. Also, initialize mx as 0.

  2. Start with the right pointer at the first element, i.e., nums[0] which is 1.

  3. Move to nums[1], which is also 1. Update cnt[1] to 2 and mx = 2.

  4. Next, we encounter nums[2] which is 2. Add to cnt and mx remains = 2.

  5. Continue to nums[3], another 2, update cnt and still mx = 2.

  6. At nums[4], the element is 4. Add to cnt and mx remains 2.

Now, the window size is r - l + 1 = 5 - 0 + 1 = 6, but mx + k = 2 + 2 = 4. Hence, we must shrink the window from the left.

  1. Increment l to point at nums[1], decrement the count of nums[0] which is 1, and window size is now 5, which is again greater than mx + k. Therefore, increment l again.

  2. Continue the process for the rest of the elements, adjusting l and r accordingly and maintaining cnt and mx.

At nums[6], the element is 4; we add it to cnt, resulting in cnt[4] being 3 and mx being updated to 3.

When the entire array has been checked with this approach, the maximum length of the possible equal subarray at any point considering at most k deletions will be retained in mx.

For the given example, after moving through the entire array with the process mentioned, you would find the maximum length to be 5, using the subarray [4, 4, 4, 2 (deleted), 2 (deleted)].

In the end, the implementation will thus return 5, the maximum length of an equal subarray, given the constraints, for array nums and integer k = 2.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def longestEqualSubarray(self, nums: List[int], k: int) -> int:
5        # Counter to store the frequency of elements in the current subarray
6        element_count = Counter()
7      
8        # Initialize the left pointer for the sliding window at position 0
9        left = 0
10      
11        # Variable to store the maximum frequency of any element in the current subarray
12        max_frequency = 0
13      
14        # Iterate through the array using 'right' as the right pointer of the sliding window
15        for right, element in enumerate(nums):
16            # Increase the count of the current element
17            element_count[element] += 1
18          
19            # Update the maximum frequency with the highest occurrence of any element so far
20            max_frequency = max(max_frequency, element_count[element])
21          
22            # Check if the window size minus the max frequency is greater than k
23            # which implies that we cannot make all elements equal within k operations
24            if right - left + 1 - max_frequency > k:
25                # Reduce the count of the leftmost element since we are going to slide the window to the right
26                element_count[nums[left]] -= 1
27              
28                # Move the left pointer of the window to the right
29                left += 1
30      
31        # Return the size of the largest window where all elements can be made equal using k operations
32        # This works because the loop maintains the largest window possible while satisfying the k constraint
33        return right - left + 1
34
1import java.util.HashMap;
2import java.util.List;
3import java.util.Map;
4
5class Solution {
6
7    /**
8     * Finds the length of the longest subarray with at most k different numbers.
9     *
10     * @param nums List of integers representing the array of numbers.
11     * @param k The maximum number of different integers allowed in the subarray.
12     * @return The length of longest subarray with at most k different numbers.
13     */
14    public int longestEqualSubarray(List<Integer> nums, int k) {
15        // A map to store the count of each number in the current window
16        Map<Integer, Integer> countMap = new HashMap<>();
17      
18        // maxFrequency stores the max frequency of a single number in the current window
19        int maxFrequency = 0;
20      
21        // Initialize the left pointer of the window
22        int left = 0;
23
24        // Iterate over the array using the right pointer
25        for (int right = 0; right < nums.size(); ++right) {
26            // Increment the count of the rightmost number in the window
27            countMap.merge(nums.get(right), 1, Integer::sum);
28          
29            // Update the max frequency if the current number's frequency is greater
30            maxFrequency = Math.max(maxFrequency, countMap.get(nums.get(right)));
31          
32            // Check if the window is invalid, i.e.,  
33            // if the number of elements that are not the same as the most frequent one is greater than k
34            if (right - left + 1 - maxFrequency > k) {
35                // If invalid, move the left pointer to the right 
36                // and decrement the count of the number at the left pointer
37                countMap.merge(nums.get(left), -1, Integer::sum);
38                left++;
39            }
40        }
41      
42        // The window size is the length of the longest subarray with at most k different numbers
43        return nums.size() - left;
44    }
45}
46
1class Solution {
2public:
3    int longestEqualSubarray(vector<int>& nums, int k) {
4        unordered_map<int, int> count; // Stores the frequency of each number encountered
5        int maxFrequency = 0; // Keeps track of the maximum frequency of any number in the current window
6        int left = 0; // Left pointer for the sliding window
7
8        // Iterate through the nums array using 'right' as the right pointer of the sliding window
9        for (int right = 0; right < nums.size(); ++right) {
10            // Update the frequency of the current number and the max frequency in the window
11            maxFrequency = max(maxFrequency, ++count[nums[right]]);
12          
13            // If the current window size minus the max frequency is greater than k
14            // It means we can't make the entire window equal by changing at most k elements
15            // So we need to slide the window
16            if (right - left + 1 - maxFrequency > k) {
17                // Before moving the left pointer, decrease the frequency of the number going out of the window
18                --count[nums[left++]];
19            }
20        }
21
22        // The size of the largest window we managed to create represents the longest subarray
23        // where we can make all elements equal by changing at most k elements
24        return right - left; // Here, 'right' is out of scope. This line should be at the end of the above for loop or right before this return statement, the value of 'right - left' should be calculated and stored.
25    }
26};
27```
28
29There is an issue with the original code's `return` statement: `mx` is returned, but it seems that the goal of the function is to return the length of the longest subarray where at most `k` elements can be changed to make the subarray all equal. The `maxFrequency` variable does not represent the size of the subarray, but rather the frequency of the most common element in the subarray. To fix this, the size of the subarray should be returned. 
30
31This is the corrected function in context:
32
33```cpp
34class Solution {
35public:
36    int longestEqualSubarray(vector<int>& nums, int k) {
37        unordered_map<int, int> count; // Stores the frequency of each number encountered
38        int maxFrequency = 0; // Keeps track of the maximum frequency of any number in the current window
39        int left = 0; // Left pointer for the sliding window
40        int maxLength = 0; // The length of the longest subarray
41
42        for (int right = 0; right < nums.size(); ++right) {
43            // Update the frequency of the current number and the max frequency in the window
44            maxFrequency = max(maxFrequency, ++count[nums[right]]);
45          
46            // If the current window size minus the max frequency is greater than k
47            // it means we can't make the entire window equal by changing at most k elements
48            // so we need to slide the window
49            while (right - left + 1 - maxFrequency > k) {
50                // Before moving the left pointer, decrease the frequency of the number going out of the window
51                --count[nums[left++]];
52            }
53          
54            // Keep track of the maximum length of subarray found so far
55            maxLength = max(maxLength, right - left + 1);
56        }
57        return maxLength; // Return the length of the longest valid subarray found
58    }
59};
60
1function longestEqualSubarray(nums: number[], k: number): number {
2    // Create a map to store the count of each number in nums
3    const countMap: Map<number, number> = new Map();
4  
5    // Variable to keep track of the maximum frequency of any number
6    let maxFrequency = 0;
7  
8    // Left pointer for the sliding window
9    let left = 0;
10  
11    // Iterate over the array with right as the right pointer of the sliding window
12    for (let right = 0; right < nums.length; ++right) {
13        // Increment the count of the current number by 1 or set it to 1 if it doesn't exist
14        countMap.set(nums[right], (countMap.get(nums[right]) ?? 0) + 1);
15      
16        // Update the maximum frequency
17        maxFrequency = Math.max(maxFrequency, countMap.get(nums[right])!);
18      
19        // If the window size minus max frequency is greater than k, shrink the window from the left
20        if (right - left + 1 - maxFrequency > k) {
21            // Decrement the count of the number at the left pointer
22            countMap.set(nums[left], countMap.get(nums[left])! - 1);
23          
24            // Move the left pointer to the right
25            left++;
26        }
27    }
28  
29    // The maximum size of the subarray is the size of the window when the loop completes
30    return right - left;
31}
32
Not Sure What to Study? Take the 2-min Quiz：

Which of these pictures shows the visit order of a depth-first search?

Time and Space Complexity

Time Complexity

The time complexity of the given code is primarily determined by the for loop which iterates through each element of the nums array once. Therefore, the complexity is dependent on the number of elements n in the nums array. Within the loop, various operations are performed in constant time, including updating the Counter, comparing and assigning the maximum value, and possibly decrementing a count in the Counter. However, as the Counter operations could in the worst case take O(n) when the Counter has grown to the size of the distinct elements in the array and we're decrementing, the dominant operation is still the for loop.

Hence, the time complexity of the code is O(n), where n is the length of the nums array.

Space Complexity

Space complexity is influenced by the additional data structures used in the algorithm. The use of a Counter to store the frequency of each distinct number results in a space complexity proportional to the number of distinct numbers in the nums array. In the worst case scenario, all numbers are distinct, leading to a space complexity equal to the number of distinct elements, which is O(n). However, if numbers repeat often, the space complexity could be much less.

Thus, the space complexity is also O(n), where n is the length of the nums array, representing the worst-case scenario where all elements are unique.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Sliding Window Maximum

https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫