Find the Longest Equal Subarray

Med

#2531Time: 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.1 company

Patterns

Algorithms

Data structures

Companies

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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]}.
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].
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.
Update Maximum: If deletions <= k, this is a valid formation. We update our global answer: maxLength = max(maxLength, count).
The final maxLength after checking all sub-lists for all numbers is the answer.

1import java.util.*;2 3class Solution {4    public int longestEqualSubarray(List<Integer> nums, int k) {5        Map<Integer, List<Integer>> positions = new HashMap<>();6        for (int i = 0; i < nums.size(); i++) {7            positions.computeIfAbsent(nums.get(i), val -> new ArrayList<>()).add(i);8        }9 10        int maxLength = 0;11        if (nums.isEmpty()) {12            return 0;13        }14 15        for (List<Integer> indices : positions.values()) {16            for (int i = 0; i < indices.size(); i++) {17                for (int j = i; j < indices.size(); j++) {18                    int count = j - i + 1;19                    // Number of elements to delete is the total span in the original array20                    // minus the count of the number we are keeping.21                    int deletions = (indices.get(j) - indices.get(i) + 1) - count;22                    if (deletions <= k) {23                        maxLength = Math.max(maxLength, count);24                    }25                }26            }27        }28        return maxLength;29    }30}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

Group Indices: Same as the previous approach, we first group indices by their value into a map: {value -> [index1, index2, ...]}.
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.
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.
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.
By processing all numbers this way, we find the overall maximum possible length.

1import java.util.*;2 3class Solution {4    public int longestEqualSubarray(List<Integer> nums, int k) {5        Map<Integer, List<Integer>> positions = new HashMap<>();6        for (int i = 0; i < nums.size(); i++) {7            positions.computeIfAbsent(nums.get(i), val -> new ArrayList<>()).add(i);8        }9 10        int maxLength = 0;11        if (nums.isEmpty()) {12            return 0;13        }14 15        for (List<Integer> indices : positions.values()) {16            int left = 0;17            for (int right = 0; right < indices.size(); right++) {18                // Number of elements to delete is the difference in original indices19                // minus the difference in positions in the 'indices' list.20                int elementsToDelete = (indices.get(right) - indices.get(left)) - (right - left);21                22                while (elementsToDelete > k) {23                    left++;24                    elementsToDelete = (indices.get(right) - indices.get(left)) - (right - left);25                }26                27                // The length of the equal subarray is the count of the target number in the window.28                maxLength = Math.max(maxLength, right - left + 1);29            }30        }31 32        return maxLength;33    }34}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int longestEqualSubarray(List<Integer> nums, int k) {4    Map<Integer, Integer> cnt = new HashMap<>();5    int mx = 0, l = 0;6    for (int r = 0; r < nums.size(); ++r) {7      cnt.merge(nums.get(r), 1, Integer : : sum);8      mx = Math.max(mx, cnt.get(nums.get(r)));9      if (r - l + 1 - mx > k) {10        cnt.merge(nums.get(l++), -1, Integer : : sum);11      }12    }13    return mx;14  }15}

1class Solution {2public:3  int longestEqualSubarray(vector<int> &nums, int k) {4    unordered_map<int, int> cnt;5    int mx = 0, l = 0;6    for (int r = 0; r < nums.size(); ++r) {7      mx = max(mx, ++cnt[nums[r]]);8      if (r - l + 1 - mx > k) {9        --cnt[nums[l++]];10      }11    }12    return mx;13  }14};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem