Maximum Equal Frequency — Solution in Python, Java & C++
Maximum Equal Frequency solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon.
Maximum Equal Frequency is a hard coding problem on arrays, hash table and counting, asked in Amazon interviews.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Counting
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of positive integers.
Return the length of the longest prefix of nums from which you can remove exactly one element so that every number still present in the prefix occurs the same number of times.
If removing that element leaves the prefix empty, it still counts: an empty selection has every (no) number occurring equally often.
Example 1
Input: nums = [4,4,7,7,9,6,6,9]
Output: 7
Explanation: The prefix `[4,4,7,7,9,6,6]` drops its single 9 to leave 4, 7 and 6 twice each. The whole array cannot work: two 9s already give every value two copies, and any removal breaks that.
Example 2
Input: nums = [5,5,5,8,8,8,2]
Output: 7
Explanation: Remove the 2: both 5 and 8 then occur three times.
Example 3
Input: nums = [1,2]
Output: 2
Explanation: Remove either element; the one left occurs once.
Constraints
2 <= nums.length <= 10^51 <= nums[i] <= 10^5
Hints for Maximum Equal Frequency
Hint 1
Track, while scanning the prefix, how often each number occurs and how many numbers have each occurrence count.
Hint 2
With
maxFthe largest occurrence count, only three shapes allow a single removal to equalise everything.Hint 3
The shapes: every count is 1; every number occurs
maxFtimes except one number that occurs once; or one number occursmaxFtimes and every other numbermaxF - 1times. Each can be checked in O(1) with the two tables.
How to solve Maximum Equal Frequency
Keep cnt[x] (occurrences of x) and freq[c] (how many numbers occur exactly c times) as the prefix grows. Whether a prefix of length L qualifies depends only on maxF and freq, through three O(1) tests.
Approach
- For each index
i, movenums[i]from countctoc + 1: decrementfreq[c], incrementfreq[c + 1], and updatemaxF. - Let
L = i + 1. The prefix qualifies ifmaxF == 1(remove any element), ormaxF * freq[maxF] == L - 1(all numbers occurmaxFtimes plus one stray element that occurs once — remove it), or(maxF - 1) * (freq[maxF - 1] + 1) == L - 1(one number occursmaxFtimes and the restmaxF - 1— remove one copy of it). - Record the last qualifying
L.
Why it works
Removing one element changes a single number's count by one. For the remaining counts to be equal, either the removed element was the only copy of its number (the others all share one count) or it reduced the unique maximum to match the rest. The two equations restate exactly those shapes as sums over freq: in each, the left side counts the elements that stay, so it must equal L - 1. All-ones is the degenerate case where any removal works.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Forgetting the single-distinct-number prefix (
[7,7,7]): it is covered by the third test withfreq[maxF - 1] = 0. - Checking only the full array: the answer is the longest qualifying prefix, so test every length.
- Exactly one element must be removed — an array whose counts are already all equal (and not all 1) does not qualify as is.
Reference solution
Python
from typing import List
def maxEqualFreq(nums: List[int]) -> int:
cnt = {}
freq = [0] * (len(nums) + 2)
max_f = 0
ans = 0
for i, x in enumerate(nums):
c = cnt.get(x, 0)
if c:
freq[c] -= 1
c += 1
cnt[x] = c
freq[c] += 1
if c > max_f:
max_f = c
if (max_f == 1 or max_f * freq[max_f] == i
or (max_f - 1) * (freq[max_f - 1] + 1) == i):
ans = i + 1
return ansJava
public static int maxEqualFreq(int[] nums) {
int n = nums.length;
int[] cnt = new int[100001];
int[] freq = new int[n + 2];
int maxF = 0, ans = 0;
for (int i = 0; i < n; i++) {
int c = cnt[nums[i]];
if (c > 0) freq[c]--;
c++;
cnt[nums[i]] = c;
freq[c]++;
maxF = Math.max(maxF, c);
if (maxF == 1 || maxF * freq[maxF] == i || (maxF - 1) * (freq[maxF - 1] + 1) == i) ans = i + 1;
}
return ans;
}C++
int maxEqualFreq(vector<int>& nums) {
int n = nums.size();
unordered_map<int, int> cnt;
vector<int> freq(n + 2, 0);
int maxF = 0, ans = 0;
for (int i = 0; i < n; i++) {
int& c = cnt[nums[i]];
if (c > 0) freq[c]--;
c++;
freq[c]++;
maxF = max(maxF, c);
if (maxF == 1 || maxF * freq[maxF] == i || (maxF - 1) * (freq[maxF - 1] + 1) == i) ans = i + 1;
}
return ans;
}JavaScript
var maxEqualFreq = function(nums) {
var cnt = new Map();
var freq = new Array(nums.length + 2).fill(0);
var maxF = 0, ans = 0;
for (var i = 0; i < nums.length; i++) {
var c = cnt.get(nums[i]) || 0;
if (c > 0) freq[c]--;
c++;
cnt.set(nums[i], c);
freq[c]++;
if (c > maxF) maxF = c;
if (maxF === 1 || maxF * freq[maxF] === i || (maxF - 1) * (freq[maxF - 1] + 1) === i) ans = i + 1;
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets