# Find the Longest Equal Subarray
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-longest-equal-subarray)
Canonical: https://scaleengineer.com/dsa/problems/find-the-longest-equal-subarray
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table
**Companies:** [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks)
---
## 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 <= 105`
* `1 <= nums[i] <= nums.length`
* `0 <= k <= nums.length`

# Approaches
## Grouping by Value with Brute-Force Check
The fundamental insight is that any valid equal subarray must consist of multiple occurrences of a single number from the original array. This allows us to process each unique number independently. This approach first groups all indices by their corresponding value and then, for each value, exhaustively checks all possible contiguous groups of its occurrences to find the longest one that satisfies the deletion constraint.
**Time:** O(N^2), where N is the number of elements in `nums`. The initial grouping takes `O(N)`. The nested loops dominate the complexity. If a number appears `c` times, the check for it takes `O(c^2)`. In the worst case, all elements are the same (`c=N`), leading to `O(N^2)` time. · **Space:** O(N), where N is the number of elements in `nums`. The `positions` map can store up to `N` indices in total across all its lists.
**Pros:** Correctly models the problem's constraints by preserving the relative order of elements.; The logic is straightforward to understand as it directly corresponds to the problem definition.
**Cons:** Inefficient for large inputs due to its quadratic time complexity, likely leading to a 'Time Limit Exceeded' error on competitive programming platforms.
### Explanation
1.  **Group Indices:** We begin by creating a map where keys are the unique numbers in `nums` and values are lists of their indices in the original array. For `nums = [1,3,2,3,1,3]`, the map would be `{1: [0, 4], 3: [1, 3, 5], 2: [2]}`.
2.  **Iterate and Check:** We then iterate through each number `v` in our map. For each `v`, we have a sorted list of its indices, `indices_v`. We use two nested loops, with pointers `i` and `j`, to select a sub-list of these indices from `indices_v[i]` to `indices_v[j]`.
3.  **Calculate Cost and Length:**
    *   The number of occurrences of `v` we are considering is `count = j - i + 1`. This is the potential length of our equal subarray.
    *   These occurrences span from original index `start = indices_v[i]` to `end = indices_v[j]`.
    *   The number of elements within this original span that are *not* `v` must be deleted. This cost is `deletions = (end - start + 1) - count`.
4.  **Update Maximum:** If `deletions <= k`, this is a valid formation. We update our global answer: `maxLength = max(maxLength, count)`.
5.  The final `maxLength` after checking all sub-lists for all numbers is the answer.

```java
import java.util.*;

class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        Map<Integer, List<Integer>> positions = new HashMap<>();
        for (int i = 0; i < nums.size(); i++) {
            positions.computeIfAbsent(nums.get(i), val -> new ArrayList<>()).add(i);
        }

        int maxLength = 0;
        if (nums.isEmpty()) {
            return 0;
        }

        for (List<Integer> indices : positions.values()) {
            for (int i = 0; i < indices.size(); i++) {
                for (int j = i; j < indices.size(); j++) {
                    int count = j - i + 1;
                    // Number of elements to delete is the total span in the original array
                    // minus the count of the number we are keeping.
                    int deletions = (indices.get(j) - indices.get(i) + 1) - count;
                    if (deletions <= k) {
                        maxLength = Math.max(maxLength, count);
                    }
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 0`.
- Create a `Map<Integer, List<Integer>>` called `positions` to store indices for each number.
- Iterate through `nums` to populate the `positions` map.
- For each `List<Integer> indices` in `positions.values()`:
  - Loop `i` from `0` to `indices.size() - 1`.
  - Loop `j` from `i` to `indices.size() - 1`.
    - `count = j - i + 1`.
    - `deletions = (indices.get(j) - indices.get(i) + 1) - count`.
    - If `deletions <= k`, update `maxLength = max(maxLength, count)`.
- Return `maxLength`.

## Sliding Window on Grouped Indices
This approach builds upon the idea of grouping indices by value but optimizes the search for the best group of occurrences. Instead of using nested loops (a brute-force check), it employs an efficient sliding window technique on the list of indices for each number.
**Time:** O(N), where N is the number of elements in `nums`. Grouping takes `O(N)`. The sliding window part involves iterating through each index list. Since each index from the original array is in exactly one list, and the `left` and `right` pointers for each list traverse it only once, the total time for all sliding windows is proportional to the sum of the lengths of the lists, which is `N`. · **Space:** O(N), where N is the number of elements in `nums`. The `positions` map stores all `N` indices, which is the dominant factor for space usage.
**Pros:** Optimal time complexity, making it highly efficient for large inputs.; Effectively avoids redundant calculations by using a sliding window, which only requires a single pass over each group of indices.
**Cons:** Requires an intermediate data structure (the map), which uses O(N) space. This might be a concern for extremely memory-constrained environments.
### Explanation
1.  **Group Indices:** Same as the previous approach, we first group indices by their value into a map: `{value -> [index1, index2, ...]}`.
2.  **Sliding Window on Indices:** For each number's list of indices, `indices_v`, we use a sliding window defined by `left` and `right` pointers. This window represents a candidate group of occurrences.
3.  **Expand and Shrink Window:**
    *   We expand the window by moving the `right` pointer forward, including one more occurrence of the number.
    *   With each expansion, we calculate the number of deletions required for the current window: `deletions = (indices_v[right] - indices_v[left]) - (right - left)`.
    *   If `deletions > k`, the window is invalid because it requires too many deletions. We must shrink the window from the left by incrementing the `left` pointer until the condition `deletions <= k` is met again.
4.  **Update Maximum:** For every valid window (i.e., after each `right` increment and any necessary `left` adjustments), the number of elements in the equal subarray is `count = right - left + 1`. We update our global maximum length with this count.
5.  By processing all numbers this way, we find the overall maximum possible length.

```java
import java.util.*;

class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        Map<Integer, List<Integer>> positions = new HashMap<>();
        for (int i = 0; i < nums.size(); i++) {
            positions.computeIfAbsent(nums.get(i), val -> new ArrayList<>()).add(i);
        }

        int maxLength = 0;
        if (nums.isEmpty()) {
            return 0;
        }

        for (List<Integer> indices : positions.values()) {
            int left = 0;
            for (int right = 0; right < indices.size(); right++) {
                // Number of elements to delete is the difference in original indices
                // minus the difference in positions in the 'indices' list.
                int elementsToDelete = (indices.get(right) - indices.get(left)) - (right - left);
                
                while (elementsToDelete > k) {
                    left++;
                    elementsToDelete = (indices.get(right) - indices.get(left)) - (right - left);
                }
                
                // The length of the equal subarray is the count of the target number in the window.
                maxLength = Math.max(maxLength, right - left + 1);
            }
        }

        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 0`.
- Create a `Map<Integer, List<Integer>>` called `positions` and populate it by iterating through `nums`.
- For each `List<Integer> indices` in `positions.values()`:
  - Initialize `left = 0`.
  - Loop `right` from `0` to `indices.size() - 1`.
    - Calculate `deletions = (indices.get(right) - indices.get(left)) - (right - left)`.
    - While `deletions > k`:
      - Increment `left`.
      - Recalculate `deletions`.
    - Update `maxLength = max(maxLength, right - left + 1)`.
- Return `maxLength`.

# Solutions
### Java

```java
class Solution {
public
  int longestEqualSubarray(List<Integer> nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    int mx = 0, l = 0;
    for (int r = 0; r < nums.size(); ++r) {
      cnt.merge(nums.get(r), 1, Integer : : sum);
      mx = Math.max(mx, cnt.get(nums.get(r)));
      if (r - l + 1 - mx > k) {
        cnt.merge(nums.get(l++), -1, Integer : : sum);
      }
    }
    return mx;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int longestEqualSubarray(vector<int> &nums, int k) {
    unordered_map<int, int> cnt;
    int mx = 0, l = 0;
    for (int r = 0; r < nums.size(); ++r) {
      mx = max(mx, ++cnt[nums[r]]);
      if (r - l + 1 - mx > k) {
        --cnt[nums[l++]];
      }
    }
    return mx;
  }
};

```

### Python

```python
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

```