Problem Description

You are given a 0-indexed integer array nums and an integer k.

The problem asks you to find the length of the longest possible equal subarray that can be formed after deleting at most k elements from nums.

An equal subarray is defined as a subarray where all elements have the same value. The empty subarray is also considered an equal subarray.

A subarray is a contiguous sequence of elements within the array (can be empty).

Key Points:

• You can delete at most k elements from the array
• After deletion, you want to find the longest contiguous sequence where all elements are equal
• The elements you delete don't have to be contiguous - you can delete any elements as long as the remaining elements form a contiguous equal subarray

Example Understanding: If you have an array like [1, 3, 1, 2, 1] and k = 1, you could delete the element 3 or 2 to get subarrays like [1, 1, 2, 1] or [1, 3, 1, 1]. The longest equal subarray you can achieve would be of length 3 (three 1's) by deleting either the 3 or the 2.

The solution uses a sliding window approach with a hash table to track element frequencies. The window maintains the property that the number of elements that need to be deleted (total elements in window minus the most frequent element count) doesn't exceed k.

Intuition

The key insight is to reframe the problem: instead of thinking about "deleting elements to form an equal subarray," we can think about it as "finding a window where one element appears frequently enough that we can delete all other elements within our budget of k deletions."

Let's think about what makes a valid equal subarray after deletions. If we have a window of size w and the most frequent element in that window appears mx times, then we need to delete w - mx elements to make all elements equal. This deletion count must be at most k.

This leads us to the sliding window approach: we can maintain a window and track the frequency of each element. As we expand the window by moving the right pointer, we keep track of the maximum frequency mx of any element in the current window.

The crucial observation is that we want to maximize the count of the most frequent element while keeping the number of deletions within budget. If a window has size r - l + 1 and the most frequent element appears mx times, then:

• Number of deletions needed = (r - l + 1) - mx
• This must satisfy: (r - l + 1) - mx ≤ k

When the deletion count exceeds k, we shrink the window from the left. The beauty of this approach is that we don't need to find which specific elements to delete - we just need to ensure that the window always maintains the property that it can be converted to an equal subarray with at most k deletions.

The answer is simply the maximum frequency mx we've seen across all valid windows, because that represents the longest equal subarray we can achieve after performing the allowed deletions.

Learn more about Binary Search and Sliding Window patterns.

Solution Approach

The solution uses a sliding window technique with a hash table to efficiently find the longest equal subarray.

Data Structures Used:

• cnt: A Counter (hash table) to track the frequency of each element in the current window
• l and r: Two pointers representing the left and right boundaries of the sliding window
• mx: Variable to track the maximum frequency of any element seen so far

Algorithm Steps:

1. Initialize variables:

   • cnt = Counter() - empty hash table for element frequencies
   • l = 0 - left pointer of the window
   • mx = 0 - maximum frequency tracker

2. Expand window with right pointer:

   • Iterate through the array using enumerate(nums) where r is the index and x is the element
   • For each element x at position r:
     • Add it to the window: cnt[x] += 1
     • Update maximum frequency: mx = max(mx, cnt[x])

3. Check and shrink window if needed:

   • Calculate current window size: r - l + 1
   • Calculate deletions needed: r - l + 1 - mx
   • If deletions needed exceed k:
     • Remove the leftmost element from the window: cnt[nums[l]] -= 1
     • Move left pointer: l += 1
     • This maintains the invariant that the window can always form an equal subarray with at most k deletions

4. Return the result:

   • After processing all elements, mx contains the length of the longest equal subarray achievable

Key Insight: The algorithm maintains a monotonically variable length window where the number of elements that need to be deleted never exceeds k. By tracking the maximum frequency across all valid windows, we find the optimal solution without explicitly determining which elements to delete.

Time Complexity: O(n) where n is the length of the array, as each element is visited at most twice (once by right pointer, once by left pointer)

Space Complexity: O(m) where m is the number of unique elements in the array, for storing the frequency map

Example Walkthrough

Let's walk through the algorithm with nums = [1, 3, 2, 3, 1, 3] and k = 2.

We want to find the longest equal subarray after deleting at most 2 elements.

Initial State:

• l = 0, mx = 0
• cnt = {}
• Window: empty

Step 1: r = 0, x = 1

• Add 1 to window: cnt = {1: 1}
• Update max frequency: mx = max(0, 1) = 1
• Window [1], size = 1
• Deletions needed: 1 - 1 = 0 ≤ 2 ✓
• Keep window

Step 2: r = 1, x = 3

• Add 3 to window: cnt = {1: 1, 3: 1}
• Update max frequency: mx = max(1, 1) = 1
• Window [1, 3], size = 2
• Deletions needed: 2 - 1 = 1 ≤ 2 ✓
• Keep window

Step 3: r = 2, x = 2

• Add 2 to window: cnt = {1: 1, 3: 1, 2: 1}
• Update max frequency: mx = max(1, 1) = 1
• Window [1, 3, 2], size = 3
• Deletions needed: 3 - 1 = 2 ≤ 2 ✓
• Keep window

Step 4: r = 3, x = 3

• Add 3 to window: cnt = {1: 1, 3: 2, 2: 1}
• Update max frequency: mx = max(1, 2) = 2
• Window [1, 3, 2, 3], size = 4
• Deletions needed: 4 - 2 = 2 ≤ 2 ✓
• Keep window

Step 5: r = 4, x = 1

• Add 1 to window: cnt = {1: 2, 3: 2, 2: 1}
• Update max frequency: mx = max(2, 2) = 2
• Window [1, 3, 2, 3, 1], size = 5
• Deletions needed: 5 - 2 = 3 > 2 ✗
• Shrink window: Remove nums[0] = 1
  • cnt = {1: 1, 3: 2, 2: 1}
  • l = 1
• New window [3, 2, 3, 1], size = 4
• Deletions needed: 4 - 2 = 2 ≤ 2 ✓

Step 6: r = 5, x = 3

• Add 3 to window: cnt = {1: 1, 3: 3, 2: 1}
• Update max frequency: mx = max(2, 3) = 3
• Window [3, 2, 3, 1, 3], size = 5
• Deletions needed: 5 - 3 = 2 ≤ 2 ✓
• Keep window

Result: mx = 3

The algorithm found that we can create an equal subarray of length 3 (three 3's) by deleting at most 2 elements (the 2 and the 1 in the window [3, 2, 3, 1, 3]).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses a sliding window approach with two pointers (l and r). The right pointer r iterates through the entire array once in the for loop, visiting each element exactly once. The left pointer l can only move forward and will move at most n times throughout the entire execution. Each operation inside the loop (counter updates, max comparison, arithmetic operations) takes O(1) time. Therefore, the overall time complexity is O(n), where n is the length of the input array nums.

Space Complexity: O(n)

The space complexity is determined by the Counter object cnt, which stores the frequency of elements within the current window. In the worst case, when all elements in the array are distinct and the window spans the entire array, the counter would need to store n different elements. Therefore, the space complexity is O(n), where n is the length of the input array.

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

Common Pitfalls

1. Incorrectly Updating Maximum Frequency After Shrinking Window

The Pitfall: A common mistake is trying to recalculate or decrement the max_frequency when shrinking the window (moving the left pointer). Some might think that if we remove an element from the window, we should update max_frequency if that element had the maximum frequency.

Why This is Wrong:

• The algorithm relies on the fact that max_frequency represents the historical maximum, not necessarily the current window's maximum frequency
• When we shrink the window, we only do so when window_size - max_frequency > k
• Even if the removed element reduces a frequency count, the window is still invalid with the current max_frequency, so we keep shrinking
• The algorithm naturally finds the correct answer because we're looking for the maximum possible equal subarray across all windows

Incorrect Implementation Example:

# WRONG - Don't do this!
if elements_to_remove > k:
    left_element = nums[left]
    frequency_map[left_element] -= 1
    # Trying to update max_frequency after removal - THIS IS WRONG
    if frequency_map[left_element] < max_frequency:
        max_frequency = max(frequency_map.values())  # Expensive and incorrect
    left += 1

Correct Approach: Keep max_frequency as is - it represents the best we've seen so far and helps maintain the optimal window size.

2. Using Counter Instead of Regular Dictionary

The Pitfall: While using Counter from collections seems natural for frequency counting, it can lead to subtle issues:

from collections import Counter

# This might seem cleaner but has a pitfall
cnt = Counter()
# ... 
cnt[nums[left]] -= 1
# Counter keeps zero and negative values, which can cause confusion

The Issue:

• Counter objects don't automatically remove keys when their count reaches 0
• This can lead to unnecessary memory usage and potential confusion when debugging

Better Approach: Use a regular dictionary with .get() method or handle zero counts explicitly:

# Clean up zero counts if needed
if frequency_map[left_element] == 0:
    del frequency_map[left_element]

3. Off-by-One Error in Window Size Calculation

The Pitfall: Forgetting to add 1 when calculating window size:

# WRONG
window_size = right - left  # Missing the +1

# CORRECT
window_size = right - left + 1

Why This Matters:

• The window from index left to right inclusive contains right - left + 1 elements
• This error would cause the algorithm to incorrectly calculate the number of deletions needed
• It could lead to accepting invalid windows or rejecting valid ones

Example: If left = 2 and right = 4, the window contains elements at indices [2, 3, 4], which is 3 elements, not 2.