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 thelongest possible equal subarray after deleting at most _k elements fromnums.

A subarray is a contiguous, possibly empty sequence of elements within an array.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5
6

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

Solution

Method 1 – Sliding Window by Value

Intuition

For each unique value, collect its indices. The problem reduces to finding the largest window of indices where the number of skipped indices (deletions) is at most k. This can be solved efficiently with a sliding window.

Approach

  1. For each unique value in nums, collect all its indices in a list.
  2. For each list, use two pointers (left, right) to find the largest window where the number of skipped indices (indices[right] - indices[left] - (right - left)) is at most k.
  3. Track the maximum window size across all values.
  4. Return the maximum size found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int longestEqualSubarray(vector<int>& nums, int k) {
        unordered_map<int, vector<int>> pos;
        for (int i = 0; i < nums.size(); ++i) pos[nums[i]].push_back(i);
        int ans = 0;
        for (auto& [v, idx] : pos) {
            int l = 0;
            for (int r = 0; r < idx.size(); ++r) {
                while (idx[r] - idx[l] - (r - l) > k) ++l;
                ans = max(ans, r - l + 1);
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func longestEqualSubarray(nums []int, k int) int {
    pos := map[int][]int{}
    for i, v := range nums {
        pos[v] = append(pos[v], i)
    }
    ans := 0
    for _, idx := range pos {
        l := 0
        for r := 0; r < len(idx); r++ {
            for idx[r]-idx[l]-(r-l) > k {
                l++
            }
            if r-l+1 > ans {
                ans = r - l + 1
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int longestEqualSubarray(int[] nums, int k) {
        Map<Integer, List<Integer>> pos = new HashMap<>();
        for (int i = 0; i < nums.length; i++) pos.computeIfAbsent(nums[i], x -> new ArrayList<>()).add(i);
        int ans = 0;
        for (var idx : pos.values()) {
            int l = 0;
            for (int r = 0; r < idx.size(); r++) {
                while (idx.get(r) - idx.get(l) - (r - l) > k) l++;
                ans = Math.max(ans, r - l + 1);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun longestEqualSubarray(nums: IntArray, k: Int): Int {
        val pos = mutableMapOf<Int, MutableList<Int>>()
        for (i in nums.indices) pos.getOrPut(nums[i]) { mutableListOf() }.add(i)
        var ans = 0
        for (idx in pos.values) {
            var l = 0
            for (r in idx.indices) {
                while (idx[r] - idx[l] - (r - l) > k) l++
                ans = maxOf(ans, r - l + 1)
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def longest_equal_subarray(nums: list[int], k: int) -> int:
    from collections import defaultdict
    pos: dict[int, list[int]] = defaultdict(list)
    for i, v in enumerate(nums):
        pos[v].append(i)
    ans = 0
    for idx in pos.values():
        l = 0
        for r in range(len(idx)):
            while idx[r] - idx[l] - (r - l) > k:
                l += 1
            ans = max(ans, r - l + 1)
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn longest_equal_subarray(nums: Vec<i32>, k: i32) -> i32 {
        use std::collections::HashMap;
        let mut pos: HashMap<i32, Vec<usize>> = HashMap::new();
        for (i, &v) in nums.iter().enumerate() {
            pos.entry(v).or_default().push(i);
        }
        let mut ans = 0;
        for idx in pos.values() {
            let mut l = 0;
            for r in 0..idx.len() {
                while idx[r] - idx[l] - (r - l) > k as usize {
                    l += 1;
                }
                ans = ans.max(r - l + 1);
            }
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    longestEqualSubarray(nums: number[], k: number): number {
        const pos: Record<number, number[]> = {};
        nums.forEach((v, i) => {
            if (!pos[v]) pos[v] = [];
            pos[v].push(i);
        });
        let ans = 0;
        for (const idx of Object.values(pos)) {
            let l = 0;
            for (let r = 0; r < idx.length; r++) {
                while (idx[r] - idx[l] - (r - l) > k) l++;
                ans = Math.max(ans, r - l + 1);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), as each index is processed at most twice.
  • 🧺 Space complexity: O(n), for storing indices by value.