Watch 10 video solutions for Find the Longest Equal Subarray, a medium level problem involving Array, Hash Table, Binary Search. This walkthrough by Prakhar Agrawal has 2,882 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |