Maximum Equal Frequency - Solution & Explanation
Problem Statement
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.
This solution iterates through the nums array, updating two frequency arrays:
- One for actual frequencies of numbers,
- Another for tracking how many numbers have a specific frequency.
At each index, we adjust these frequencies and check conditions for equalizing frequencies upon removal.
Complexity
Time complexity: O(N), where N is the length of nums.
Space complexity: O(N), for the frequency arrays.
Approach 2: Approach 2: Prefix Consideration
In this approach, we evaluate prefixes of the array to directly track optimal removals.
This solution considers the prefix incrementally and aims at altering the frequency table by either removing an element from high-frequency to low, or from unique to balance count.
It's a more straightforward approach in terms of implementation, and while it utilizes a similar idea to the first approach, utilizes prefix-based shuffling of frequency values.
This C solution focuses on handling the prefix incrementally, applying removal logic once a critical point is hit among frequency counts. It is a more iterative and shuffling approach.
Complexity
Time complexity: O(N)
Space complexity: O(N)
Approach 3: 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.
Code
Python
Java
C++
Go
TypeScript
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 arrays. |
| Approach 2: Prefix Consideration | Time complexity: O(N) Space complexity: O(N) |
| Array or Hash Table | — |
Detailed 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. |
Video Solution
LeetCode 1224. Maximum Equal Frequency Explanation and Solution • happygirlzt • 3,143 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Equal Frequency easy or hard?
Maximum Equal Frequency Python/Java solution
How to solve Maximum Equal Frequency in O(n)?
What is the best approach for Maximum Equal Frequency?
Is Maximum Equal Frequency asked at Google/Amazon/Meta?
What data structure is used in Maximum Equal Frequency?
What is the time complexity of Maximum Equal Frequency?
Ready to solve this problem?
Practice Maximum Equal Frequency with our built-in code editor and test cases.
Practice on FleetCode