2831. Find the Longest Equal Subarray
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.
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:
- A counter named
cnt
is initialized usingCounter
from the collections module. This counter will keep track of the frequency of each element within the current window. - Two pointers,
l
(left) andr
(right), are used to define the boundaries of the sliding window.l
starts at 0, andr
is incremented in each iteration of the for loop. - A variable
mx
, initialized at 0, is used to store the maximum frequency of any element within the current window throughout the iterations. - The main loop iterates over the indices and values from the
nums
array. Asr
moves to the right, the corresponding valuex
innums
is added to thecnt
counter. - After each new element is added to
cnt
, themx
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. - At any point, if the size of the current window (given by
r - l + 1
) minus the maximum frequency (mx
) exceedsk
, 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 incrementingl
and decrementing the frequency of thel
th element incnt
. - 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. - Finally, the length of the longest possible equal subarray (
mx
) that satisfies the condition after deleting at mostk
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
Initialize the counter
cnt
and pointersl = 0
,r = 0
. Also, initializemx
as 0. -
Start with the right pointer at the first element, i.e.,
nums[0]
which is 1. -
Move to
nums[1]
, which is also 1. Updatecnt[1]
to 2 andmx = 2
. -
Next, we encounter
nums[2]
which is 2. Add tocnt
andmx remains = 2
. -
Continue to
nums[3]
, another 2, updatecnt
and stillmx = 2
. -
At
nums[4]
, the element is 4. Add tocnt
andmx
remains2
.
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.
-
Increment
l
to point atnums[1]
, decrement the count ofnums[0]
which is 1, and window size is now 5, which is again greater thanmx + k
. Therefore, incrementl
again. -
Continue the process for the rest of the elements, adjusting
l
andr
accordingly and maintainingcnt
andmx
.
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
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.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
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
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!