Maximum Equal Frequency solution and explanation
9 more videos on this problem
LeetCode 1224. Maximum Equal Frequency Explanation and Solutionhappygirlzt · 7:54 · 3K views
LeetCode 1224. [HARD] Maximum Equal FrequencyDream FAANG · 1:01:21 · 921 views
LeetCode 1224. Maximum Equal Frequency 中文解释 Chinese Versionhappygirlzt · 8:01 · 655 views
【每日一题】LeetCode 1224. Maximum Equal FrequencyHuifeng Guan · 29:24 · 487 views
Leetcode--1224 maximum equal frequency (Hashmap)You Wu · 23:43 · 461 views
Leetcode 1224. Maximum Equal FrequencyFearless Learner · 16:55 · 244 views
Leetcode 1224 Maximum Equal FrequencyCoder on A Farm · 17:25 · 216 views
LeetCode 1224 – Maximum Equal Frequency | Best Intuition + Optimal SolutionCodehurdle · 30:34 · 139 views
LeetCode 1224 - Maxium Equal Frequency - PythonAlpha-Code · 20:04 · 101 views
LeetCode Hard 1224 Maximum Equal Frequencyrobzingcod · 52:29 · 18 views
The 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).
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 <= 1051 <= nums[i] <= 105
Approach overview
Problem Overview: You are given an integer array nums. For every prefix of the array, check whether removing exactly one element can make the remaining numbers appear with equal frequency. The goal is to return the maximum prefix length that satisfies this condition.
Approach 1: Frequency Maps (O(n) time, O(n) space)
This approach maintains two hash maps while scanning the array from left to right. The first map count[x] stores how many times each number appears. The second map freq[f] stores how many numbers currently have frequency f. Every time you process a new element, you update both maps: decrement the old frequency bucket and increment the new one.
The key insight is that only a few patterns allow equal frequencies after removing one element. These include cases where all numbers appear once, one number appears once while the rest share the same higher frequency, or exactly one number has frequency one greater than the others. After each update, check whether the current prefix length satisfies one of these patterns. Because each step performs constant-time hash lookup and updates, the total complexity remains O(n) time with O(n) extra space.
This technique heavily relies on efficient counting using a hash table. It works well for large arrays because it avoids recomputing frequencies from scratch for each prefix.
Approach 2: Prefix Consideration (O(n) time, O(n) space)
This method focuses on validating prefixes while iterating through the array. You maintain the frequency of each value and track the current maximum frequency seen so far. Instead of checking all elements, the logic evaluates whether the prefix length can be explained by one of the valid equal-frequency structures.
For example, a prefix is valid if every number appears once, or if removing one occurrence from a value with the maximum frequency aligns all counts. Using prefix length, maximum frequency, and counts of numbers with specific frequencies, you can quickly determine if the condition holds. Each step requires only constant-time updates and comparisons.
The algorithm processes the array once, making it O(n) time with O(n) space for frequency storage. The approach blends prefix analysis with counting techniques commonly used in array and hash table problems.
Recommended for interviews: The frequency map approach is what most interviewers expect. It demonstrates understanding of counting patterns and careful reasoning about edge cases. A brute force approach that recomputes frequencies for every prefix shows the basic idea but runs in O(n^2). The optimized hash-map solution proves you can derive constant-time prefix validation and handle tricky frequency states efficiently.
Approach 1: Approach 1: Frequency Maps
In this approach, we'll use two hash maps to keep track of the frequency of each number seen so far, and the frequency of those frequencies.
We'll iterate though the array while maintaining these mappings. At every step, we'll check if it's possible to remove one element such that the remaining numbers have equal frequency.
We can do this by ensuring either: all numbers have the same frequency, or one number can have a frequency of one greater or lesser than others. This must hold true throughout, so we evaluate it at each step.
from collections import defaultdict
def maxEqualFreq(nums):
freq = defaultdict(int)
count = defaultdict(int)
max_freq = res = 0
for i, num in enumerate(nums):
count[freq[num]] -= 1
freq[num] += 1
count[freq[num]] += 1
max_freq = max(max_freq, freq[num])
if count[max_freq] * max_freq == i + 1 and i < len(nums) - 1:
res = i + 2
if count[max_freq] == 1 and count[max_freq - 1] * (max_freq - 1) == i:
res = i + 1
return res
nums = [2,2,1,1,5,3,3,5]
print(maxEqualFreq(nums))import java.util.*;
public class MaxEqualFreq {
public static int maxEqualFreq(int[] nums) {
Map<Integer, Integer> freq = new HashMap<>();
Map<Integer, Integer> count = new HashMap<>();
int maxFreq = 0, res = 0;
for (int i = 0; i < nums.length; ++i) {
int num = nums[i];
count.put(freq.getOrDefault(num, 0), count.getOrDefault(freq.getOrDefault(num, 0), 0) - 1);
freq.put(num, freq.getOrDefault(num, 0) + 1);
count.put(freq.get(num), count.getOrDefault(freq.get(num), 0) + 1);
maxFreq = Math.max(maxFreq, freq.get(num));
if (count.get(maxFreq) * maxFreq == i + 1 && i < nums.length - 1) res = i + 2;
if (count.get(maxFreq) == 1 && count.getOrDefault(maxFreq - 1, 0) * (maxFreq - 1) == i) res = i + 1;
}
return res;
}
public static void main(String[] args) {
int[] nums = {2,2,1,1,5,3,3,5};
System.out.println(maxEqualFreq(nums));
}
}#include <unordered_map>
#include <iostream>
#include <vector>
using namespace std;
int maxEqualFreq(vector<int>& nums) {
unordered_map<int, int> freq, count;
int maxFreq = 0, res = 0;
for (int i = 0; i < nums.size(); ++i) {
int num = nums[i];
count[freq[num]]--;
freq[num]++;
count[freq[num]]++;
maxFreq = max(maxFreq, freq[num]);
if (count[maxFreq] * maxFreq == i + 1 && i < nums.size() - 1) res = i + 2;
if (count[maxFreq] == 1 && count[maxFreq - 1] * (maxFreq - 1) == i) res = i + 1;
}
return res;
}
int main() {
vector<int> nums = {2,2,1,1,5,3,3,5};
cout << maxEqualFreq(nums) << endl;
return 0;
}function maxEqualFreq(nums) {
const freq = {};
const count = {};
let maxFreq = 0, res = 0;
for (let i = 0; i < nums.length; ++i) {
const num = nums[i];
if (!count[freq[num]]) count[freq[num]] = 0;
count[freq[num]]--;
freq[num] = (freq[num] || 0) + 1;
count[freq[num]] = (count[freq[num]] || 0) + 1;
maxFreq = Math.max(maxFreq, freq[num]);
if (count[maxFreq] * maxFreq === i + 1 && i < nums.length - 1) res = i + 2;
if (count[maxFreq] === 1 && count[maxFreq - 1] * (maxFreq - 1) === i) res = i + 1;
}
return res;
}
const nums = [2, 2, 1, 1, 5, 3, 3, 5];
console.log(maxEqualFreq(nums));#include <stdio.h>
#include <string.h>
#define MAX 100001
int maxEqualFreq(int* nums, int numsSize) {
int freq[MAX] = {0};
int count[MAX] = {0};
int maxFreq = 0, res = 0;
for (int i = 0; i < numsSize; i++) {
int num = nums[i];
count[freq[num]]--;
freq[num]++;
count[freq[num]]++;
if (freq[num] > maxFreq) maxFreq = freq[num];
if (count[maxFreq] * maxFreq == i + 1 && i < numsSize - 1) {
res = i + 2;
}
if (count[maxFreq] == 1 && count[maxFreq - 1] * (maxFreq - 1) == i) {
res = i + 1;
}
}
return res;
}
int main() {
int nums[] = {2,2,1,1,5,3,3,5};
int length = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maxEqualFreq(nums, length));
return 0;
}using System;
using System.Collections.Generic;
public class MaxEqualFreq {
public static int MaxEqualFrequency(int[] nums) {
var freq = new Dictionary<int, int>();
var count = new Dictionary<int, int>();
int maxFreq = 0, res = 0;
for (int i = 0; i < nums.Length; ++i) {
int num = nums[i];
if (!count.ContainsKey(freq.GetValueOrDefault(num, 0)))
count[freq.GetValueOrDefault(num, 0)] = 0;
count[freq.GetValueOrDefault(num, 0)]--;
freq[num] = freq.GetValueOrDefault(num, 0) + 1;
if (!count.ContainsKey(freq[num]))
count[freq[num]] = 0;
count[freq[num]]++;
maxFreq = Math.Max(maxFreq, freq[num]);
if (count[maxFreq] * maxFreq == i + 1 && i < nums.Length - 1) res = i + 2;
if (count[maxFreq] == 1 && count.GetValueOrDefault(maxFreq - 1, 0) * (maxFreq - 1) == i) res = i + 1;
}
return res;
}
public static void Main() {
int[] nums = { 2, 2, 1, 1, 5, 3, 3, 5 };
Console.WriteLine(MaxEqualFrequency(nums));
}
}The Python implementation uses default dictionaries to track the frequency of each number and the frequency of those frequencies. It evaluates possible conditions for making numbers have equal frequency by removing one element.
Time complexity: O(N), where N is the length of nums.
Space complexity: O(N), for the frequency dictionaries.
Approach 2: Array or Hash Table
We use cnt to record the number of times each element v appears in nums, and ccnt to record the number of times each count appears. The maximum number of times an element appears is represented by mx.
While traversing nums:
- If the maximum count
mx=1, it means that each number in the current prefix appears1time. If we delete any one of them, the remaining numbers will all have the same count. - If all numbers appear
mxandmx-1times, and only one number appearsmxtimes, then we can delete one occurrence of the number that appearsmxtimes. The remaining numbers will all have a count ofmx-1, which meets the condition. - If, except for one number, all other numbers appear
mxtimes, then we can delete the number that appears once. The remaining numbers will all have a count ofmx, which meets the condition.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the nums array.
function maxEqualFreq(nums: number[]): number {
const n = nums.length;
const map = new Map();
for (const num of nums) {
map.set(num, (map.get(num) ?? 0) + 1);
}
for (let i = n - 1; i > 0; i--) {
for (const k of map.keys()) {
map.set(k, map.get(k) - 1);
let num = 0;
for (const v of map.values()) {
if (v !== 0) {
num = v;
break;
}
}
let isOk = true;
let sum = 1;
for (const v of map.values()) {
if (v !== 0 && v !== num) {
isOk = false;
break;
}
sum += v;
}
if (isOk) {
return sum;
}
map.set(k, map.get(k) + 1);
}
map.set(nums[i], map.get(nums[i]) - 1);
}
return 1;
}func maxEqualFreq(nums []int) int {
cnt := map[int]int{}
ccnt := map[int]int{}
ans, mx := 0, 0
for i, v := range nums {
i++
if cnt[v] > 0 {
ccnt[cnt[v]]--
}
cnt[v]++
mx = max(mx, cnt[v])
ccnt[cnt[v]]++
if mx == 1 {
ans = i
} else if ccnt[mx]*mx+ccnt[mx-1]*(mx-1) == i && ccnt[mx] == 1 {
ans = i
} else if ccnt[mx]*mx+1 == i && ccnt[1] == 1 {
ans = i
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Frequency Maps | Time complexity: O(N), where N is the length of nums. Space complexity: O(N), for the frequency dictionaries. |
| Array or Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Maps | O(n) | O(n) | General case. Best for tracking dynamic frequency updates while scanning the array. |
| Prefix Consideration | O(n) | O(n) | When reasoning about prefix validity conditions using maximum frequency and count distribution. |
Frequently asked questions
Is Maximum Equal Frequency easy or hard?
Maximum Equal Frequency is classified as a hard problem because it requires recognizing specific frequency patterns that allow equal counts after removing one element. The implementation is short but the reasoning behind the valid cases is non-trivial.
Maximum Equal Frequency Python/Java solution
Python and Java implementations typically use a dictionary or HashMap for counting numbers and another map for frequency-of-frequency tracking. The algorithm iterates once through the array and checks valid frequency configurations at each prefix.
How to solve Maximum Equal Frequency in O(n)?
Iterate through the array while maintaining two maps: one for element frequency and another for how many elements have a given frequency. Track the current maximum frequency and check whether the prefix can form equal frequencies after removing one element. Each prefix check is constant time, leading to O(n) total complexity.
What is the best approach for Maximum Equal Frequency?
The best approach uses two hash maps to track element frequencies and how many numbers share the same frequency. While scanning the array once, you update these counts and check a few valid patterns that allow equal frequencies after removing one element. This solution runs in O(n) time and O(n) space.
Is Maximum Equal Frequency asked at Google/Amazon/Meta?
Maximum Equal Frequency is a hard-level frequency counting problem similar to questions asked at companies like Google, Amazon, and Meta. It tests hash map usage, reasoning about frequency distributions, and careful handling of edge cases.
What data structure is used in Maximum Equal Frequency?
Hash maps are the primary data structure. One map stores the frequency of each number, and another tracks how many numbers share the same frequency. This structure allows constant-time updates and quick validation of prefix conditions.
What is the time complexity of Maximum Equal Frequency?
The optimal solution runs in O(n) time because the array is processed once and each step performs constant-time hash map updates. Space complexity is O(n) in the worst case to store frequency counts of distinct numbers.