Maximum Equal Frequency - Video Solutions

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.