Skip to main content
Talentd

Find the Longest Equal Subarray - Solution & Explanation

MediumArrayHash TableBinary SearchSliding Window17 min readAsked at: Microsoft, Palo Alto Networks, Mathworks
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Sliding Window Technique

The sliding window technique maintains a window of possible equal elements. Starting with two pointers, the window is extended from the left while maintaining the condition that at most k elements need be removed to form an equal subarray. Incrementally update the window's length to find the maximum equal subarray.

This C implementation utilizes a hashmap to track the frequency of elements within the window. It adjusts the left pointer to ensure no more than k elements outside the most frequent can be in the window, finding the maximum possible equal subarray length.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(n), for the count array.

Try this approach in the editor →

Approach 2: Hash Map with Frequency Check

This approach mirrors the sliding window but optimizes by focusing on hashmap access and frequency management. The computational load remains with index adjustments and ensuring the deletions don't exceed k for a consistent equal subarray.

The C solution uses a static array of frequencies, reducing the computational overhead vs dynamic structures. It maximizes the window size while reducing the necessity of adjustments for calculations of equal subarrays.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the nums array length.
Space Complexity: O(n), resulting from the storage in the frequency array.

Try this approach in the editor →

Approach 3: 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.

The number of all elements in the window minus the number of the most frequently occurring element in the window is the number of elements that need to be deleted from the window.

Each time, we add the element pointed to by the right pointer to the window, then update the hash table, and also update the number of the most frequently occurring element in the window. When the number of elements that need to be deleted from the window exceeds k, we move the left pointer once, and then update the hash table.

After the traversal, return the number of the most frequently occurring element.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Technique

Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(n), for the count array.

Hash Map with Frequency Check

Time Complexity: O(n), where n is the nums array length.
Space Complexity: O(n), resulting from the storage in the frequency array.

Hash Table + Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window on Value PositionsO(n)O(n)Best general solution when you group indices for each value and control deletions using two pointers.
Hash Map Frequency Sliding WindowO(n)O(n)Useful when applying the classic window constraint window_size - max_frequency ≤ k.
Brute Force Subarray CheckO(n²)O(n)Only for conceptual understanding or very small arrays.

Video Solution

Leetcode Weekly contest 359 - Medium- Find the Longest Equal Subarray • Prakhar Agrawal • 2,967 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Longest Equal Subarray easy or hard?
The problem is classified as Medium difficulty. The challenge comes from recognizing the sliding window constraint that limits how many elements can be removed. Once the frequency tracking idea is clear, the implementation is straightforward.
Find the Longest Equal Subarray Python/Java solution
Both Python and Java implementations typically use a sliding window with a hash map. Python uses collections.Counter or defaultdict for frequency tracking, while Java uses HashMap<Integer, Integer>. The algorithm runs in O(n) time and handles large arrays efficiently.
How to solve Find the Longest Equal Subarray in O(n)?
Use a sliding window with a hash map that stores element frequencies. Expand the right pointer and update the frequency of the current number. If window_size minus the maximum frequency becomes greater than k, move the left pointer until the window becomes valid again. Track the maximum frequency seen during this process.
What is the best approach for Find the Longest Equal Subarray?
The optimal solution uses a sliding window technique combined with frequency tracking. Maintain a window and track the most frequent element inside it. If window_size minus max_frequency exceeds k, move the left pointer. This keeps the deletions within limit and runs in O(n) time.
Is Find the Longest Equal Subarray asked at Google/Amazon/Meta?
Sliding window and frequency optimization problems like this appear frequently in interviews at companies such as Amazon, Google, and Meta. Variants that involve maximizing a uniform segment after limited removals or replacements are common in coding rounds.
What data structure is used in Find the Longest Equal Subarray?
The main data structure is a hash map used to track element frequencies or store indices of each value. Combined with the sliding window technique, it allows efficient updates and constant‑time lookups while scanning the array.
What is the time complexity of Find the Longest Equal Subarray?
The optimal sliding window solution runs in O(n) time because each element is processed at most twice by the two pointers. Space complexity is O(n) in the worst case due to storing frequencies or index groups in a hash map.

Ready to solve this problem?

Practice Find the Longest Equal Subarray with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays