LeetCode 1224 - Maximum Equal Frequency

LeetCode Problem 1224

Difficulty: 🔴 Hard
Topics: Array, Hash Table

Solution

Problem Understanding

The problem gives an array nums consisting of positive integers. We must find the longest prefix of the array such that, after removing exactly one element from that prefix, every remaining number appears the same number of times.

A prefix means the subarray starting from index 0 and ending at some index i. We are free to choose any prefix length, and we want the maximum possible one.

The important detail is that we remove exactly one element, not one distinct value. We remove a single occurrence of some number. After that removal, all remaining numbers that still exist in the prefix must have identical frequencies.

For example, consider the prefix:

[2,2,1,1,5,3,3]

The frequencies are:

2 -> 2
1 -> 2
5 -> 1
3 -> 2

If we remove the single 5, the remaining frequencies become:

2 -> 2
1 -> 2
3 -> 2

All remaining numbers now appear exactly twice, so this prefix is valid.

The constraints are large:

• nums.length can be up to 10^5
• values can also be up to 10^5

These constraints immediately rule out expensive recomputation for every prefix. Any solution worse than roughly O(n log n) will likely time out. The intended solution is linear time.

Several edge cases are important:

• A prefix where every number appears once is always valid, because removing any one element leaves all remaining frequencies equal.
• A prefix with only one distinct number is always valid, because removing one occurrence still leaves a valid configuration.
• A valid prefix may require removing the element with the highest frequency.
• A valid prefix may instead require removing the only element with frequency 1.
• We must remove exactly one element, even if the frequencies are already equal.

The challenge is recognizing, in constant time per prefix, whether the current frequency distribution can become uniform after one removal.

Approaches

Brute Force Approach

A brute-force solution would examine every possible prefix of the array.

For each prefix:

1. Count the frequency of every number.
2. Try removing one occurrence of every distinct number.
3. After each hypothetical removal, check whether all remaining frequencies are equal.
4. If any removal works, the prefix is valid.

This approach is correct because it directly simulates the problem definition. For every prefix, it exhaustively tests all possible removals and verifies the resulting frequencies.

However, it is far too slow.

Suppose the array length is n. There are O(n) prefixes. For each prefix, we may have O(n) distinct numbers. For each removal attempt, we may again scan frequencies to verify equality.

The total complexity can easily reach O(n^2) or worse, which is infeasible for n = 10^5.

Optimal Approach

The key insight is that we do not need to fully recompute frequencies for every prefix. Instead, we can maintain two pieces of information incrementally:

1. count[num]

• How many times each number appears.

2. freq[f]

• How many numbers currently appear exactly f times.

This second structure is the crucial optimization.

For example:

count:
1 -> 2
2 -> 2
3 -> 1

freq:
1 -> 1
2 -> 2

This means:

• one number appears once
• two numbers appear twice

Using these aggregated statistics, we can recognize the only possible valid patterns.

A prefix is valid if one of these conditions holds:

1. Every number appears once.
2. Exactly one number appears once, and all others share the same higher frequency.
3. Exactly one number has frequency one greater than all others.

These conditions can be checked in constant time while processing the array once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) to O(n³)	O(n)	Recomputes and validates frequencies for every prefix
Optimal	O(n)	O(n)	Maintains frequency-of-frequency counts incrementally

Algorithm Walkthrough

1. Create two hash maps:

• count[num] stores how many times each number has appeared.
• freq[f] stores how many numbers currently have frequency f.

2. Initialize:

• max_frequency = 0
• best = 0

max_frequency tracks the largest frequency seen in the current prefix. 3. Iterate through the array one element at a time. 4. For the current number:

• Let its old frequency be old_freq.
• Decrease freq[old_freq] because this number is about to move to a higher frequency.
• Increase its count in count.
• Let the new frequency be new_freq.
• Increase freq[new_freq].

5. Update max_frequency if needed.
6. Let:

• length = current index + 1

We now test whether the current prefix can become uniform after removing exactly one element. 7. Check the first valid pattern:

• Every number appears exactly once.

This means:

max_frequency == 1

Example:

[1,2,3,4]

Removing any element leaves all remaining numbers with frequency 1. 8. Check the second valid pattern:

• One number appears once.
• All other numbers appear max_frequency times.

This condition is:

freq[1] == 1
and
freq[max_frequency] * max_frequency + 1 == length

Example:

[1,1,2,2,3]

Frequencies:

1 -> 2
2 -> 2
3 -> 1

Removing 3 makes all remaining frequencies equal. 9. Check the third valid pattern:

• Exactly one number has frequency max_frequency.
• All other numbers have frequency max_frequency - 1.

This condition is:

freq[max_frequency] == 1
and
freq[max_frequency - 1] * (max_frequency - 1) + max_frequency == length

Example:

[1,1,1,2,2,2,3,3,3,4]

Frequencies:

1 -> 3
2 -> 3
3 -> 3
4 -> 1

Removing one occurrence from the number with highest frequency restores uniformity. 10. If any condition is true:

• Update best = length.

11. Continue until the end of the array.
12. Return best.

Why it works

At any prefix, only a very small set of frequency distributions can become perfectly uniform after removing one element.

Either:

• all frequencies are already 1,
• one value occurs once too few,
• or one value occurs once too many.

The algorithm tracks the distribution of frequencies directly using freq, allowing these patterns to be verified in constant time for every prefix. Since every possible valid configuration must match one of these cases, the algorithm is correct.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        count = defaultdict(int)
        freq = defaultdict(int)

        max_frequency = 0
        best = 0

        for i, num in enumerate(nums):
            old_freq = count[num]

            if old_freq > 0:
                freq[old_freq] -= 1

            count[num] += 1
            new_freq = count[num]

            freq[new_freq] += 1

            max_frequency = max(max_frequency, new_freq)

            length = i + 1

            # Case 1:
            # Every number appears exactly once
            if max_frequency == 1:
                best = length

            # Case 2:
            # One number appears once,
            # all others appear max_frequency times
            elif (
                freq[1] == 1
                and freq[max_frequency] * max_frequency + 1 == length
            ):
                best = length

            # Case 3:
            # One number appears max_frequency times,
            # all others appear max_frequency - 1 times
            elif (
                freq[max_frequency] == 1
                and (
                    freq[max_frequency - 1] * (max_frequency - 1)
                    + max_frequency
                    == length
                )
            ):
                best = length

        return best

The implementation closely follows the algorithm described earlier.

count tracks the frequency of each number. Whenever a number is processed, its old frequency bucket is decremented and its new frequency bucket is incremented.

freq is the critical optimization. Instead of repeatedly scanning all counts, it tells us how many numbers currently share the same frequency.

max_frequency keeps track of the largest frequency in the current prefix. This allows the algorithm to evaluate the three valid configurations efficiently.

The three conditional blocks correspond exactly to the three valid structural patterns:

• all frequencies equal to 1
• one singleton value
• one value exceeding the others by exactly one occurrence

Whenever one of these conditions is satisfied, the current prefix length becomes a candidate answer.

Because each element is processed once and every update is constant time, the entire algorithm runs in linear time.

Go Solution

package main

func maxEqualFreq(nums []int) int {
	count := make(map[int]int)
	freq := make(map[int]int)

	maxFrequency := 0
	best := 0

	for i, num := range nums {
		oldFreq := count[num]

		if oldFreq > 0 {
			freq[oldFreq]--
		}

		count[num]++
		newFreq := count[num]

		freq[newFreq]++

		if newFreq > maxFrequency {
			maxFrequency = newFreq
		}

		length := i + 1

		// Case 1:
		// Every number appears exactly once
		if maxFrequency == 1 {
			best = length

		} else if freq[1] == 1 &&
			freq[maxFrequency]*maxFrequency+1 == length {

			// Case 2:
			// One number appears once,
			// all others appear maxFrequency times
			best = length

		} else if freq[maxFrequency] == 1 &&
			freq[maxFrequency-1]*(maxFrequency-1)+maxFrequency == length {

			// Case 3:
			// One number appears maxFrequency times,
			// all others appear maxFrequency - 1 times
			best = length
		}
	}

	return best
}

The Go implementation mirrors the Python logic almost exactly.

Go uses built-in maps instead of defaultdict, so missing keys naturally return 0, which works perfectly for frequency counting.

All integer operations remain within safe bounds because the maximum array length is only 10^5.

The logic for maintaining frequency buckets and validating the three structural patterns is identical to the Python solution.

Worked Examples

Example 1

Input:

nums = [2,2,1,1,5,3,3,5]

We process prefixes one by one.

Step	Number	count	freq	max_frequency	Valid?	Best
1	2	{2:1}	{1:1}	1	Yes	1
2	2	{2:2}	{2:1}	2	Yes	2
3	1	{2:2,1:1}	{1:1,2:1}	2	Yes	3
4	1	{2:2,1:2}	{2:2}	2	No	3
5	5	{2:2,1:2,5:1}	{1:1,2:2}	2	Yes	5
6	3	{2:2,1:2,5:1,3:1}	{1:2,2:2}	2	No	5
7	3	{2:2,1:2,5:1,3:2}	{1:1,2:3}	2	Yes	7
8	5	{2:2,1:2,5:2,3:2}	{2:4}	2	No	7

Final answer:

7

Example 2

Input:

nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]

Final frequencies at length 13:

1 -> 3
2 -> 3
3 -> 3
4 -> 3
5 -> 1

The frequency map becomes:

1 -> 1
3 -> 4

There is exactly one number with frequency 1, and every other number appears 3 times.

Removing 5 produces:

1 -> 3
2 -> 3
3 -> 3
4 -> 3

So the entire array of length 13 is valid.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed once with constant-time hash map updates
Space	O(n)	Frequency maps may store up to O(n) distinct values

The algorithm performs a single pass through the array. Each iteration updates two hash maps and checks a constant number of conditions.

No nested iteration or recomputation of frequencies occurs, which keeps the runtime linear.

The auxiliary space depends on the number of distinct values and distinct frequencies, both of which are bounded by n.

Test Cases

sol = Solution()

assert sol.maxEqualFreq([2,2,1,1,5,3,3,5]) == 7
# Provided example 1

assert sol.maxEqualFreq([1,1,1,2,2,2,3,3,3,4,4,4,5]) == 13
# Provided example 2

assert sol.maxEqualFreq([1,2,3,4,5]) == 5
# All numbers unique

assert sol.maxEqualFreq([1,1,1,1]) == 4
# Single distinct number

assert sol.maxEqualFreq([1,1,2,2,3]) == 5
# Remove the single-frequency element

assert sol.maxEqualFreq([1,1,2,2,2]) == 5
# Remove one occurrence from the highest-frequency element

assert sol.maxEqualFreq([1,2]) == 2
# Smallest valid mixed array

assert sol.maxEqualFreq([1,1]) == 2
# Smallest repeated array

assert sol.maxEqualFreq([1,1,2,3,3]) == 5
# Multiple frequencies, valid after one removal

assert sol.maxEqualFreq([1,1,2,2,3,3,4,4,5,5,5]) == 11
# One value exceeds all others by one

assert sol.maxEqualFreq([10]) == 1
# Single-element array

Test	Why
[2,2,1,1,5,3,3,5]	Validates the classic singleton-removal scenario
[1,1,1,2,2,2,3,3,3,4,4,4,5]	Tests large balanced groups plus one singleton
[1,2,3,4,5]	Every frequency is already 1
[1,1,1,1]	Single distinct value edge case
[1,1,2,2,3]	Tests removing a singleton element
[1,1,2,2,2]	Tests reducing the highest-frequency value
[1,2]	Minimal mixed input
[1,1]	Minimal repeated input
[1,1,2,3,3]	Mixed distribution validation
[1,1,2,2,3,3,4,4,5,5,5]	One value exceeds others by one
[10]	Single-element boundary case

Edge Cases

One important edge case occurs when every number appears exactly once. For example:

[1,2,3,4]

A naive implementation may incorrectly think no removal is needed. However, the problem requires removing exactly one element. After removing any element, all remaining numbers still appear exactly once. The implementation handles this with the condition:

max_frequency == 1

Another important edge case occurs when there is only one distinct value. For example:

[5,5,5,5]

Removing any single occurrence leaves:

[5,5,5]

which is still perfectly uniform. Some implementations incorrectly assume multiple distinct numbers are required. The frequency-based conditions naturally handle this scenario correctly.

A third tricky edge case occurs when one number has frequency exactly one greater than the others. For example:

[1,1,2,2,2]

The frequencies are:

1 -> 2
2 -> 3

Removing one 2 makes both frequencies equal to 2. The implementation explicitly checks for this structure using:

freq[max_frequency] == 1

combined with the total-length validation formula.

Another subtle case is when the prefix is already perfectly balanced, such as:

[1,1,2,2]

Even though all frequencies are equal, removing one element breaks the equality. Therefore this prefix is not valid. The implementation avoids this mistake because none of the three valid structural conditions match this configuration.