Find the Longest Equal Subarray

Problem Description

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.

Key Insights

• A subarray can be transformed into an equal subarray by removing up to k elements.
• The problem can be efficiently solved using a sliding window technique.
• A frequency count of elements can help determine the maximum length of an equal subarray after deletions.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a sliding window approach along with a frequency map (or dictionary). The idea is to maintain a window that represents the current subarray we are examining. We also keep track of the count of the most frequent element within this window.

1. Initialize two pointers, left and right, to represent the window's boundaries.
2. Use a frequency map to count occurrences of each element in the current window.
3. Expand the right pointer to include more elements and update the frequency map.
4. If the number of elements that need to be deleted to make the subarray equal exceeds k, move the left pointer to shrink the window from the left.
5. Throughout this process, keep track of the maximum length of the equal subarray found.

This algorithm ensures that we check each element at most twice (once by the left pointer and once by the right pointer), leading to a linear time complexity.

Code Solutions