2831. Find the Longest Equal Subarray - Solution

Q: 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.

Q: 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 . The algorithm runs in O(n) time and handles large arrays efficiently.

The problem

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 <= 10⁵
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.

Python

def longestEqualSubarray(nums, k):
    count = {}
    maxLen = 0
    maxFreq = 0
    left = 0
    for right in range(len(nums)):
        count[nums[right]] = count.get(nums[right], 0) + 1
        maxFreq = max(maxFreq, count[nums[right]])
        if right - left + 1 - maxFreq > k:
            count[nums[left]] -= 1
            left += 1
        maxLen = max(maxLen, right - left + 1)
    return maxLen

nums = [1, 3, 2, 3, 1, 3]
k = 3
print(longestEqualSubarray(nums, k))

Java

import java.util.HashMap;

public class LongestEqualSubarray {
    public static int longestEqualSubarray(int[] nums, int k) {
        HashMap<Integer, Integer> count = new HashMap<>();
        int maxLen = 0, maxFreq = 0;
        for (int left = 0, right = 0; right < nums.length; right++) {
            count.put(nums[right], count.getOrDefault(nums[right], 0) + 1);
            maxFreq = Math.max(maxFreq, count.get(nums[right]));
            while (right - left + 1 - maxFreq > k) {
                count.put(nums[left], count.get(nums[left]) - 1);
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 2, 3, 1, 3};
        int k = 3;
        System.out.println(longestEqualSubarray(nums, k));
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int longestEqualSubarray(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    int maxLen = 0, maxFreq = 0;
    for(int left = 0, right = 0; right < nums.size(); right++) {
        maxFreq = max(maxFreq, ++count[nums[right]]);
        while (right - left + 1 - maxFreq > k) {
            count[nums[left]]--;
            left++;
        }
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

int main() {
    vector<int> nums = {1, 3, 2, 3, 1, 3};
    int k = 3;
    cout << longestEqualSubarray(nums, k) << endl;
    return 0;
}

JavaScript

function longestEqualSubarray(nums, k) {
    const count = {};
    let maxLen = 0;
    let maxFreq = 0;
    let left = 0;
    for (let right = 0; right < nums.length; right++) {
        count[nums[right]] = (count[nums[right]] || 0) + 1;
        maxFreq = Math.max(maxFreq, count[nums[right]]);
        while (right - left + 1 - maxFreq > k) {
            count[nums[left]]--;
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

const nums = [1, 3, 2, 3, 1, 3];
const k = 3;
console.log(longestEqualSubarray(nums, k));

#include <stdio.h>

int longestEqualSubarray(int* nums, int numsSize, int k) {
    int maxLen = 0, maxFreq = 0;
    int count[numsSize + 1];  
    for(int i = 0; i <= numsSize; i++)
        count[i] = 0;
    for (int left = 0, right = 0; right < numsSize; right++) {
        maxFreq = count[nums[right]] = count[nums[right]] + 1;
        if (right - left + 1 - maxFreq > k) {
            maxFreq = count[nums[left]] = count[nums[left]] - 1;
            left++;
        }
        maxLen = right - left + 1;
    }
    return maxLen;
}

int main() {
    int nums[] = {1, 3, 2, 3, 1, 3};
    int k = 3;
    int result = longestEqualSubarray(nums, 6, k);
    printf("%d\n", result);
    return 0;
}

using System;
using System.Collections.Generic;

class Program {
    public static int LongestEqualSubarray(int[] nums, int k) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        int maxLen = 0, maxFreq = 0;
        int left = 0;
        for (int right = 0; right < nums.Length; right++) {
            if (!count.ContainsKey(nums[right]))
                count[nums[right]] = 0;
            count[nums[right]]++;
            maxFreq = Math.Max(maxFreq, count[nums[right]]);
            while (right - left + 1 - maxFreq > k) {
                count[nums[left]]--;
                left++;
            }
            maxLen = Math.Max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    static void Main(string[] args) {
        int[] nums = { 1, 3, 2, 3, 1, 3 };
        int k = 3;
        Console.WriteLine(LongestEqualSubarray(nums, k));
    }
}

This Python function tracks element counts using a dictionary. The sliding window is enlarged and shrunk through two pointers while ensuring the condition regarding the number of deletions relative to the most occurring element.

Complexity

Time Complexity: O(n), with n representing the number of elements in the input list.
Space Complexity: O(n), needed for dictionary that tracks element frequencies.

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.

Python

def longestEqualSubarray(nums, k):
    frequency = {}
    maxLen = 0
    maxFreq = 0
    left = 0
    for right in range(len(nums)):
        frequency[nums[right]] = frequency.get(nums[right], 0) + 1
        maxFreq = max(maxFreq, frequency[nums[right]])
        if right - left + 1 - maxFreq > k:
            frequency[nums[left]] -= 1
            left += 1
        maxLen = max(maxLen, right - left + 1)
    return maxLen

nums = [1, 3, 2, 3, 1, 3]
k = 3
print(longestEqualSubarray(nums, k))

Java

import java.util.HashMap;

public class LongestEqualSubarray {
    public static int longestEqualSubarray(int[] nums, int k) {
        HashMap<Integer, Integer> frequency = new HashMap<>();
        int maxLen = 0, maxFreq = 0;
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            frequency.put(nums[right], frequency.getOrDefault(nums[right], 0) + 1);
            maxFreq = Math.max(maxFreq, frequency.get(nums[right]));
            if (right - left + 1 - maxFreq > k) {
                frequency.put(nums[left], frequency.get(nums[left]) - 1);
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 2, 3, 1, 3};
        int k = 3;
        System.out.println(longestEqualSubarray(nums, k));
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int longestEqualSubarray(vector<int>& nums, int k) {
    unordered_map<int, int> frequency;
    int maxLen = 0, maxFreq = 0;
    int left = 0;
    for(int right = 0; right < nums.size(); right++) {
        frequency[nums[right]]++;
        maxFreq = max(maxFreq, frequency[nums[right]]);
        if (right - left + 1 - maxFreq > k) {
            frequency[nums[left]]--;
            left++;
        }
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

int main() {
    vector<int> nums = {1, 3, 2, 3, 1, 3};
    int k = 3;
    cout << longestEqualSubarray(nums, k) << endl;
    return 0;
}

JavaScript

function longestEqualSubarray(nums, k) {
    const frequency = {};
    let maxLen = 0;
    let maxFreq = 0;
    let left = 0;
    for (let right = 0; right < nums.length; right++) {
        frequency[nums[right]] = (frequency[nums[right]] || 0) + 1;
        maxFreq = Math.max(maxFreq, frequency[nums[right]]);
        if (right - left + 1 - maxFreq > k) {
            frequency[nums[left]]--;
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

const nums = [1, 3, 2, 3, 1, 3];
const k = 3;
console.log(longestEqualSubarray(nums, k));

#include <stdio.h>

int longestEqualSubarray(int* nums, int numsSize, int k) {
    int maxLen = 0, maxFreq = 0;
    int frequency[numsSize + 1];  
    for(int i = 0; i <= numsSize; i++)
        frequency[i] = 0;
    int left = 0;
    for (int right = 0; right < numsSize; right++) {
        maxFreq = frequency[nums[right]] = frequency[nums[right]] + 1;
        if (right - left + 1 - maxFreq > k) {
            maxFreq = frequency[nums[left]] = frequency[nums[left]] - 1;
            left++;
        }
        maxLen = maxLen > (right - left + 1) ? maxLen : (right - left + 1);
    }
    return maxLen;
}

int main() {
    int nums[] = {1, 3, 2, 3, 1, 3};
    int k = 3;
    int result = longestEqualSubarray(nums, 6, k);
    printf("%d\n", result);
    return 0;
}

using System;
using System.Collections.Generic;

class Program {
    public static int LongestEqualSubarray(int[] nums, int k) {
        Dictionary<int, int> frequency = new Dictionary<int, int>();
        int maxLen = 0, maxFreq = 0;
        int left = 0;
        for (int right = 0; right < nums.Length; right++) {
            if (!frequency.ContainsKey(nums[right]))
                frequency[nums[right]] = 0;
            frequency[nums[right]]++;
            maxFreq = Math.Max(maxFreq, frequency[nums[right]]);
            if (right - left + 1 - maxFreq > k) {
                frequency[nums[left]]--;
                left++;
            }
            maxLen = Math.Max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    static void Main(string[] args) {
        int[] nums = { 1, 3, 2, 3, 1, 3 };
        int k = 3;
        Console.WriteLine(LongestEqualSubarray(nums, k));
    }
}

The Python method leverages a dictionary to tabulate occurrences, ensuring the window's condition criteria. It efficiently computes maximum subarray length with a minimal deletion threshold.

Complexity

Time Complexity: O(n), given element traversal within nums.
Space Complexity: O(n), resulting from dictionary operations.

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.

TypeScript

function longestEqualSubarray(nums: number[], k: number): number {
    const cnt: Map<number, number> = new Map();
    let mx = 0;
    let l = 0;
    for (let r = 0; r < nums.length; ++r) {
        cnt.set(nums[r], (cnt.get(nums[r]) ?? 0) + 1);
        mx = Math.max(mx, cnt.get(nums[r])!);
        if (r - l + 1 - mx > k) {
            cnt.set(nums[l], cnt.get(nums[l])! - 1);
            ++l;
        }
    }
    return mx;
}

func longestEqualSubarray(nums []int, k int) int {
	cnt := map[int]int{}
	mx, l := 0, 0
	for r, x := range nums {
		cnt[x]++
		mx = max(mx, cnt[x])
		if r-l+1-mx > k {
			cnt[nums[l]]--
			l++
		}
	}
	return mx
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sliding Window Technique	Time Complexity: O(n), with n representing the number of elements in the input list. Space Complexity: O(n), needed for dictionary that tracks element frequencies.
Hash Map with Frequency Check	Time Complexity: O(n), given element traversal within nums. Space Complexity: O(n), resulting from dictionary operations.
Hash Table + Two Pointers	–

Complexity analysis

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

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.

Find the Longest Equal Subarray solution and explanation

The problem

Approach overview

Approach 1: Sliding Window Technique

Approach 2: Hash Map with Frequency Check

Approach 3: Hash Table + Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find the Longest Equal Subarray solution and explanation

The problem

Approach overview

Approach 1: Sliding Window Technique

Approach 2: Hash Map with Frequency Check

Approach 3: Hash Table + Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems