LeetCode 2831 - Find the Longest Equal Subarray

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Binary Search, Sliding Window

Solution

Problem Understanding

The problem asks us to find the longest contiguous subarray where all elements are equal, after we are allowed to delete at most k elements from the original array. In simpler terms, we are trying to create the longest block of identical numbers by optionally removing some disruptive numbers, up to k deletions.

The input consists of an integer array nums of length up to 10^5 and an integer k that specifies the maximum number of elements we can remove. Each element in nums is guaranteed to be between 1 and nums.length. The output is a single integer representing the length of the longest equal subarray possible under the given deletion limit.

Key observations include:

The array can be large, so any solution with time complexity worse than O(n log n) or O(n) is likely too slow.
Since deletions are allowed, the problem is related to sliding window techniques: we can consider "stretching" a window of equal numbers by deleting elements that break the equality.
Edge cases to consider are when k = 0 (no deletions allowed), when all elements are already equal, and when k is greater than or equal to the array length (the answer will be the full array length).

Approaches

Brute-force approach: Iterate over every possible subarray, count the occurrences of each element, and check whether it can be transformed into an equal subarray with at most k deletions. While correct, this requires examining O(n^2) subarrays and computing element frequencies for each, giving O(n^3) or O(n^2) depending on implementation. This is infeasible for n = 10^5.

Optimal approach: The key insight is that we can treat each number independently. For each unique number x in nums, we use a sliding window to find the longest contiguous block that can be made equal to x by deleting at most k other numbers. This works because deleting non-x elements is equivalent to counting how many non-x elements exist in a window and keeping it ≤ k.

By iterating through all distinct numbers and applying this sliding window, we efficiently find the maximum equal subarray length.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(1)	Examine all subarrays, count deletions needed to make them equal
Optimal	O(n * u)	O(u)	`u` is the number of unique numbers; sliding window for each number

Algorithm Walkthrough

Identify all unique numbers in nums. For each unique number x, we want to find the longest contiguous subarray where all elements can be converted to x by deleting at most k other numbers.
Initialize two pointers left = 0 and right = 0 to maintain the sliding window, and a counter non_x_count to track how many elements in the current window are not equal to x.
Expand the right pointer by moving right forward. If nums[right] != x, increment non_x_count.
If non_x_count exceeds k, shrink the window from the left by moving left forward and decrement non_x_count if the element being removed is not x.
After adjusting the window, update the maximum window length found for this number as max_length = max(max_length, right - left + 1).
Repeat steps 2-5 for all unique numbers.
Return the largest maximum length among all numbers.

Why it works: For each number, the sliding window ensures that the number of deletions needed does not exceed k. By considering all unique numbers, we guarantee that the globally longest equal subarray is found.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def longestEqualSubarray(self, nums: List[int], k: int) -> int:
        max_length = 0
        unique_nums = set(nums)
        
        for x in unique_nums:
            left = 0
            non_x_count = 0
            
            for right in range(len(nums)):
                if nums[right] != x:
                    non_x_count += 1
                
                while non_x_count > k:
                    if nums[left] != x:
                        non_x_count -= 1
                    left += 1
                
                max_length = max(max_length, right - left + 1)
        
        return max_length

Explanation: We loop over each unique value in nums. The sliding window [left, right] maintains at most k elements that are not equal to x. Whenever the number of non-x elements exceeds k, we shrink the window from the left. At every step, we update the max_length based on the size of the current valid window.

Go Solution

func longestEqualSubarray(nums []int, k int) int {
    maxLength := 0
    uniqueNums := make(map[int]struct{})
    for _, num := range nums {
        uniqueNums[num] = struct{}{}
    }

    for x := range uniqueNums {
        left := 0
        nonXCount := 0

        for right := 0; right < len(nums); right++ {
            if nums[right] != x {
                nonXCount++
            }

            for nonXCount > k {
                if nums[left] != x {
                    nonXCount--
                }
                left++
            }

            if right-left+1 > maxLength {
                maxLength = right - left + 1
            }
        }
    }

    return maxLength
}

Go-specific notes: We use a map to store unique numbers because Go does not have a built-in set. Slices handle window indices naturally. Integer overflow is not a concern here due to the problem constraints.

Worked Examples

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

Iterate through unique numbers {1,2,3}.

For x = 1: sliding window produces max length 2.
For x = 2: max length 1.
For x = 3: max length 3 (delete indices 2 and 4).

Output is 3.

Example 2: nums = [1,1,2,2,1,1], k = 2

For x = 1: max length 4 (delete indices 2 and 3).
For x = 2: max length 2.

Output is 4.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * u)	`u` is the number of unique numbers, for each number we slide over the array once
Space	O(u)	Storing unique numbers in a set/map

The time complexity is efficient for arrays with limited unique elements. In the worst case, u = n, giving O(n^2), but for typical scenarios with repeated values, it is much faster.

Test Cases

# Provided examples
assert Solution().longestEqualSubarray([1,3,2,3,1,3], 3) == 3  # example 1
assert Solution().longestEqualSubarray([1,1,2,2,1,1], 2) == 4  # example 2

# Edge cases
assert Solution().longestEqualSubarray([1], 0) == 1  # single element, no deletion
assert Solution().longestEqualSubarray([1,2,3,4], 0) == 1  # no deletions allowed, all unique
assert Solution().longestEqualSubarray([1,1,1,1], 2) == 4  # all same already
assert Solution().longestEqualSubarray([1,2,1,2,1,2], 3) == 4  # mix, must delete some
assert Solution().longestEqualSubarray([1,2,3,4,5], 5) == 5  # k >= n, can delete all but one type

Test	Why
[1,3,2,3,1,3], k=3	checks basic sliding window logic
[1,1,2,2,1,1], k=2	tests merging non-consecutive blocks
[1], k=0	smallest array edge case
[1,2,3,4], k=0	no deletions allowed, all elements unique
[1,1,1,1], k=2	array already equal
[1,2,1,2,1,2], k=3	mix requiring deletions
[1,2,3,4,5], k=5	deletion limit larger than array

Edge Cases

Array of length 1: The result must always be 1 regardless of k. The implementation correctly handles this by the sliding window not needing any movement.
No deletions allowed (k = 0): The algorithm handles this because the window shrinks as soon as non_x_count exceeds zero.
All elements the same: The algorithm