#2831

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find the Longest Equal Subarray

Find the maximum length of an equal subarray after removing up to k elements using array scanning and hash-based index tracking.

array hash table binary search sliding window

Problem Statement

You are given an integer array nums and an integer k. A subarray is called equal if all elements in the subarray are identical. Your task is to determine the maximum length of an equal subarray that can be obtained by deleting at most k elements from nums.

For example, given nums and k, you can selectively remove up to k elements to form the longest contiguous sequence of identical numbers. Return the length of this longest possible equal subarray after these deletions. Consider all combinations of deletions to ensure the maximum length is achieved.

Examples

Example 1

Input: nums = [1,3,2,3,1,3], k = 3

Output: 3

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

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 <= 105
1 <= nums[i] <= nums.length
0 <= k <= nums.length

Solution Approach

Build index maps for each unique value

For each number x in nums, create a sorted list of indices where nums[i] equals x. This allows direct access to potential subarrays of identical elements without scanning unrelated numbers.

Use sliding window to check deletions

For each value's index list, apply a sliding window to count how many elements must be removed to make the window contiguous. Expand the window until the number of deletions exceeds k, then slide forward to maintain feasibility.

Track maximum equal subarray length

As you process each value's window, calculate the subarray length after deletions and update the global maximum. This ensures the answer reflects the longest achievable equal subarray under the k-deletion constraint.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of unique values and their occurrences, roughly O(n) to build maps and slide windows. Space complexity is O(n) for storing index lists of each unique element.

What Interviewers Usually Probe

Watch for off-by-one errors when counting deletions within the sliding window.
Expect discussion about mapping values to index lists for efficient lookups.
Be prepared to explain why contiguous windows capture maximum equal subarrays after deletions.

Common Pitfalls or Variants

Common pitfalls

Forgetting to account for deletions at the edges of the window, leading to underestimated lengths.
Attempting to scan the original array repeatedly instead of using precomputed index lists.
Ignoring cases where multiple disjoint subarrays of the same value compete for maximum length.

Follow-up variants

Instead of deleting up to k elements, allow swapping k elements to maximize the equal subarray.
Return the actual subarray, not just its length, after optimal deletions.
Apply the same logic to 2D grids to find the longest equal row or column segment after removing k elements.

FAQ

What is the main pattern for solving Find the Longest Equal Subarray?

The problem relies on array scanning combined with hash-based index tracking for each unique value, enabling efficient window evaluation.

Can the subarray be empty?

Yes, an empty subarray counts as an equal subarray, but typically the maximum length is achieved with at least one element.

How do we efficiently handle large arrays?

Use hash maps to store indices for each number and sliding windows on these lists, which avoids repeatedly scanning the full array.

Does the order of elements matter after deletion?

Yes, deletions must maintain the original order to form contiguous equal subarrays.

What happens if k is larger than necessary?

Extra deletions beyond what is needed to form the longest equal subarray have no effect; the maximum length is still constrained by existing sequences.

terminal

Solution

Solution 1: Hash Table + Two Pointers

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.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def longestEqualSubarray(self, nums: List[int], k: int) -> int:
        cnt = Counter()
        l = 0
        mx = 0
        for r, x in enumerate(nums):
            cnt[x] += 1
            mx = max(mx, cnt[x])
            if r - l + 1 - mx > k:
                cnt[nums[l]] -= 1
                l += 1
        return mx

Solution 2: Hash Table + Two Pointers (Method 2)

We can use a hash table $g$ to maintain the index list of each element.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def longestEqualSubarray(self, nums: List[int], k: int) -> int:
        cnt = Counter()
        l = 0
        mx = 0
        for r, x in enumerate(nums):
            cnt[x] += 1
            mx = max(mx, cnt[x])
            if r - l + 1 - mx > k:
                cnt[nums[l]] -= 1
                l += 1
        return mx

Continue Practicing

#3134 find the median of the uniqueness array #2009 minimum number of operations to make array continuous #2830 maximize the profit as the salesman