Maximum Equal Frequency
HardUpdated: Aug 2, 2025
Practice on:
Problem
Given an array nums of positive integers, return the longest possible length of an array prefix of nums, such that it is possible to remove exactly one element from this prefix so that every number that has appeared in it will have the same number of occurrences.
If after removing one element there are no remaining elements, it's still considered that every appeared number has the same number of ocurrences (0).
Examples
Example 1
Input: nums = [2,2,1,1,5,3,3,5]
Output: 7
Explanation: For the subarray [2,2,1,1,5,3,3] of length 7, if we remove nums[4] = 5, we will get [2,2,1,1,3,3], so that each number will appear exactly twice.
Example 2
Input: nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]
Output: 13
Constraints
2 <= nums.length <= 10^51 <= nums[i] <= 10^5
Solution
Method 1 – Hash Map and Frequency Counting
Intuition
We want to find the longest prefix such that, after removing one element, all numbers have the same frequency. By tracking the count of each number and the count of each frequency, we can check at each step if the prefix is valid.
Approach
- Use a hash map to count occurrences of each number (
cnt). - Use another hash map to count how many numbers have each frequency (
freq). - For each index in
nums, updatecntandfreqfor the current number. - At each step, check if the prefix can be made valid by removing one element:
- All numbers have frequency 1.
- Only one number has frequency 1, and the rest have the same frequency.
- Only one number has a frequency greater by 1 than the rest, and it occurs once.
- Keep track of the maximum valid prefix length.
Code
C++
class Solution {
public:
int maxEqualFreq(vector<int>& nums) {
unordered_map<int, int> cnt, freq;
int ans = 0, n = nums.size();
for (int i = 0; i < n; ++i) {
int x = nums[i];
if (cnt[x]) freq[cnt[x]]--;
cnt[x]++;
freq[cnt[x]]++;
int f1 = freq[1], f2 = freq[cnt[x]], maxf = cnt[x];
int total = i+1;
if (maxf == 1 ||
(freq[maxf]*maxf + freq[maxf-1]*(maxf-1) == total && freq[maxf] == 1) ||
(freq[1] == 1 && freq[maxf]*maxf + freq[maxf-1]*(maxf-1) == total-1))
ans = total;
}
return ans;
}
};
Go
func maxEqualFreq(nums []int) int {
cnt := map[int]int{}
freq := map[int]int{}
ans := 0
for i, x := range nums {
if cnt[x] > 0 {
freq[cnt[x]]--
}
cnt[x]++
freq[cnt[x]]++
maxf := cnt[x]
total := i+1
if maxf == 1 ||
(freq[maxf]*maxf+freq[maxf-1]*(maxf-1) == total && freq[maxf] == 1) ||
(freq[1] == 1 && freq[maxf]*maxf+freq[maxf-1]*(maxf-1) == total-1) {
ans = total
}
}
return ans
}
Java
class Solution {
public int maxEqualFreq(int[] nums) {
Map<Integer, Integer> cnt = new HashMap<>(), freq = new HashMap<>();
int ans = 0;
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
if (cnt.getOrDefault(x, 0) > 0) freq.put(cnt.get(x), freq.get(cnt.get(x))-1);
cnt.put(x, cnt.getOrDefault(x, 0)+1);
freq.put(cnt.get(x), freq.getOrDefault(cnt.get(x), 0)+1);
int maxf = cnt.get(x), total = i+1;
if (maxf == 1 ||
(freq.getOrDefault(maxf,0)*maxf + freq.getOrDefault(maxf-1,0)*(maxf-1) == total && freq.getOrDefault(maxf,0) == 1) ||
(freq.getOrDefault(1,0) == 1 && freq.getOrDefault(maxf,0)*maxf + freq.getOrDefault(maxf-1,0)*(maxf-1) == total-1))
ans = total;
}
return ans;
}
}
Kotlin
class Solution {
fun maxEqualFreq(nums: IntArray): Int {
val cnt = mutableMapOf<Int, Int>()
val freq = mutableMapOf<Int, Int>()
var ans = 0
for ((i, x) in nums.withIndex()) {
if (cnt[x] != null && cnt[x]!! > 0) freq[cnt[x]!!] = freq.getOrDefault(cnt[x]!!, 0) - 1
cnt[x] = cnt.getOrDefault(x, 0) + 1
freq[cnt[x]!!] = freq.getOrDefault(cnt[x]!!, 0) + 1
val maxf = cnt[x]!!
val total = i+1
if (maxf == 1 ||
(freq.getOrDefault(maxf,0)*maxf + freq.getOrDefault(maxf-1,0)*(maxf-1) == total && freq.getOrDefault(maxf,0) == 1) ||
(freq.getOrDefault(1,0) == 1 && freq.getOrDefault(maxf,0)*maxf + freq.getOrDefault(maxf-1,0)*(maxf-1) == total-1))
ans = total
}
return ans
}
}
Python
class Solution:
def maxEqualFreq(self, nums: list[int]) -> int:
from collections import defaultdict
cnt = defaultdict(int)
freq = defaultdict(int)
ans = 0
for i, x in enumerate(nums):
if cnt[x]:
freq[cnt[x]] -= 1
cnt[x] += 1
freq[cnt[x]] += 1
maxf = cnt[x]
total = i+1
if maxf == 1 or \
(freq[maxf]*maxf + freq[maxf-1]*(maxf-1) == total and freq[maxf] == 1) or \
(freq[1] == 1 and freq[maxf]*maxf + freq[maxf-1]*(maxf-1) == total-1):
ans = total
return ans
Rust
impl Solution {
pub fn max_equal_freq(nums: Vec<i32>) -> i32 {
use std::collections::HashMap;
let mut cnt = HashMap::new();
let mut freq = HashMap::new();
let mut ans = 0;
for (i, &x) in nums.iter().enumerate() {
if let Some(&c) = cnt.get(&x) {
*freq.entry(c).or_insert(0) -= 1;
}
let c = cnt.entry(x).or_insert(0);
*c += 1;
*freq.entry(*c).or_insert(0) += 1;
let maxf = *c;
let total = i+1;
if maxf == 1 ||
(freq.get(&maxf).unwrap_or(&0)*maxf as i32 + freq.get(&(maxf-1)).unwrap_or(&0)*(maxf-1) as i32 == total as i32 && *freq.get(&maxf).unwrap_or(&0) == 1) ||
(*freq.get(&1).unwrap_or(&0) == 1 && freq.get(&maxf).unwrap_or(&0)*maxf as i32 + freq.get(&(maxf-1)).unwrap_or(&0)*(maxf-1) as i32 == total as i32 - 1) {
ans = total as i32;
}
}
ans
}
}
TypeScript
class Solution {
maxEqualFreq(nums: number[]): number {
const cnt = new Map<number, number>(), freq = new Map<number, number>();
let ans = 0;
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
if (cnt.has(x) && cnt.get(x)! > 0) freq.set(cnt.get(x)!, (freq.get(cnt.get(x)!) ?? 0) - 1);
cnt.set(x, (cnt.get(x) ?? 0) + 1);
freq.set(cnt.get(x)!, (freq.get(cnt.get(x)!) ?? 0) + 1);
const maxf = cnt.get(x)!;
const total = i+1;
if (maxf == 1 ||
((freq.get(maxf) ?? 0)*maxf + (freq.get(maxf-1) ?? 0)*(maxf-1) == total && (freq.get(maxf) ?? 0) == 1) ||
((freq.get(1) ?? 0) == 1 && (freq.get(maxf) ?? 0)*maxf + (freq.get(maxf-1) ?? 0)*(maxf-1) == total-1))
ans = total;
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n), wherenis the length of the array, as we process each element once. - 🧺 Space complexity:
O(n), for the hash maps.