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] <= 105The key idea in #1224 Maximum Equal Frequency is to process the array from left to right and determine the longest prefix where removing at most one element can make all remaining numbers appear the same number of times. To achieve this efficiently, we maintain two hash maps: one to track the frequency of each number and another to track how many numbers have a particular frequency.
While iterating through the array, update these structures and keep track of the current maximum frequency. At each step, check whether the current prefix can form a valid configuration where all numbers have equal frequency after removing at most one element. This typically happens in cases such as: all numbers appearing once, only one number having a higher frequency, or exactly one number appearing once while others share a common frequency.
By validating these patterns during iteration, we can track the maximum valid prefix length in O(n) time using hash tables, with O(n) space for frequency bookkeeping.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map Frequency Tracking | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Keep track of the min and max frequencies.
The number to be eliminated must have a frequency of 1, same as the others or the same +1.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems involving frequency counting and prefix validation are common in FAANG-style interviews. Maximum Equal Frequency tests hash map usage, pattern recognition, and edge case reasoning, which are core skills for technical interviews.
Hash tables are the most effective data structure for this problem. One map stores the frequency of each number, while another tracks how many numbers share the same frequency. This structure enables constant-time updates and checks during iteration.
The optimal approach uses two hash maps to track element frequencies and the count of those frequencies. While scanning the array, you check specific patterns where removing one element can make all remaining frequencies equal. This allows the problem to be solved in linear time.
Tracking the frequency of frequencies helps quickly determine if the current prefix satisfies conditions where equal frequency can be achieved after removing one element. It allows us to validate patterns such as one element having a unique frequency or all others sharing the same count.