You are given a 0-indexed integer array nums and an integer k.
A subarray is called equal if all of its elements are equal. Note that the empty subarray is an equal subarray.
Return the length of the longest possible equal subarray after deleting at most k elements from nums.
A subarray is a contiguous, possibly empty sequence of elements within an array.
Example 1:
Input: nums = [1,3,2,3,1,3], k = 3 Output: 3 Explanation: It's optimal to delete the elements at index 2 and index 4. After deleting them, nums becomes equal to [1, 3, 3, 3]. The longest equal subarray starts at i = 1 and ends at j = 3 with length equal to 3. It can be proven that no longer equal subarrays can be created.
Example 2:
Input: nums = [1,1,2,2,1,1], k = 2 Output: 4 Explanation: It's optimal to delete the elements at index 2 and index 3. After deleting them, nums becomes equal to [1, 1, 1, 1]. The array itself is an equal subarray, so the answer is 4. It can be proven that no longer equal subarrays can be created.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= nums.length0 <= k <= nums.lengthProblem Overview: You are given an integer array nums and an integer k. You may delete at most k elements from a subarray so that the remaining elements are all equal. The task is to return the maximum possible length of such an equal subarray.
Approach 1: Sliding Window on Value Positions (O(n) time, O(n) space)
This method groups indices of each value using a map, then runs a sliding window over those indices. For a value x, take its positions array and expand a window with two pointers. The number of deletions needed equals the gap between the current indices minus the number of elements already in the window. If required deletions exceed k, move the left pointer forward. The window size represents how many equal elements can remain after deleting the gaps. This approach works well because only positions of identical numbers are considered, avoiding unnecessary comparisons. It uses a hash table to group indices and a sliding window to maintain the valid range.
Approach 2: Hash Map Frequency Sliding Window (O(n) time, O(n) space)
This approach scans the array once while maintaining a dynamic window using two pointers. A hash map stores frequencies of values inside the window and tracks the most frequent element. If the window size minus the maximum frequency exceeds k, too many deletions would be required, so the left pointer moves forward and frequencies update. The length of the equal subarray that can remain equals the maximum frequency within the valid window. This pattern is common in array problems where you transform a window by removing or replacing elements to satisfy a constraint. It is straightforward to implement and performs well for large inputs.
Recommended for interviews: The sliding window solution is the expected answer. Interviewers want to see that you recognize the constraint window_size - max_frequency ≤ k or use the index-gap trick for each value. A brute force attempt (checking every subarray) shows initial reasoning but runs in O(n²). The optimized sliding window demonstrates strong understanding of two‑pointer techniques and frequency tracking.
The sliding window technique maintains a window of possible equal elements. Starting with two pointers, the window is extended from the left while maintaining the condition that at most k elements need be removed to form an equal subarray. Incrementally update the window's length to find the maximum equal subarray.
This C implementation utilizes a hashmap to track the frequency of elements within the window. It adjusts the left pointer to ensure no more than k elements outside the most frequent can be in the window, finding the maximum possible equal subarray length.
Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(n), for the count array.
This approach mirrors the sliding window but optimizes by focusing on hashmap access and frequency management. The computational load remains with index adjustments and ensuring the deletions don't exceed k for a consistent equal subarray.
The C solution uses a static array of frequencies, reducing the computational overhead vs dynamic structures. It maximizes the window size while reducing the necessity of adjustments for calculations of equal subarrays.
Time Complexity: O(n), where n is the nums array length.
Space Complexity: O(n), resulting from the storage in the frequency array.
We use two pointers to maintain a monotonically variable length window, and a hash table to maintain the number of occurrences of each element in the window.
The number of all elements in the window minus the number of the most frequently occurring element in the window is the number of elements that need to be deleted from the window.
Each time, we add the element pointed to by the right pointer to the window, then update the hash table, and also update the number of the most frequently occurring element in the window. When the number of elements that need to be deleted from the window exceeds k, we move the left pointer once, and then update the hash table.
After the traversal, return the number of the most frequently occurring element.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window Technique | Time Complexity: O(n), where n is the length of nums. |
| Hash Map with Frequency Check | Time Complexity: O(n), where n is the nums array length. |
| Hash Table + Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window on Value Positions | O(n) | O(n) | Best general solution when you group indices for each value and control deletions using two pointers. |
| Hash Map Frequency Sliding Window | O(n) | O(n) | Useful when applying the classic window constraint window_size - max_frequency ≤ k. |
| Brute Force Subarray Check | O(n²) | O(n) | Only for conceptual understanding or very small arrays. |
Leetcode Weekly contest 359 - Medium- Find the Longest Equal Subarray • Prakhar Agrawal • 2,882 views views
Watch 9 more video solutions →Practice Find the Longest Equal Subarray with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor