LeetCode Solutions Blog

Maximum Equal Frequency

Number: 1344

Difficulty: Hard

Paid? No

Problem Description

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. Note that if after removing one element there are no remaining elements, it’s still considered valid because every (zero) number has the same frequency.

Key Insights

Use a hash table (dictionary) to count occurrences of each number.
Use another hash table to count how many numbers have a specific frequency.
As you iterate over the prefix, update both hash tables.
At each step, check a few conditions that would allow the array (after one removal) to have equal frequencies:
- All numbers occur only once.
- All numbers have the same frequency except one number that occurs exactly once.
- All numbers have the same frequency except one number that has one more occurrence than the others.
Update the maximum valid prefix length when any of these conditions hold.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements, because we process each element in constant time. Space Complexity: O(n), owing to the storage required for the hash tables.

Solution

We will iterate through the nums array and maintain two hash maps:

count: maps each number to its frequency.
freq: maps each frequency to the count of numbers with that frequency.

For each element in the prefix:

Increase its count.
Update the freq hash table accordingly.
Check whether the current state satisfies one of the valid conditions:
- When all numbers are seen once.
- When there is exactly one number with frequency 1 and all other numbers have the same frequency.
- When there is exactly one number with a frequency that is one greater than the frequency of all other numbers. If any condition is satisfied, record the current index as the longest valid prefix.

Code Solutions

# Python solution for Maximum Equal Frequency

class Solution:
    def maxEqualFreq(self, nums):
        # Dictionary to count the frequency of each number
        count = {}
        # Dictionary to count how many numbers have a given frequency
        freq = {}
        # Variable to track the longest valid prefix length
        best = 0
        # Variable to track the maximum frequency seen so far
        max_freq = 0
        
        # Iterate over the array elements with index
        for i, num in enumerate(nums):
            # Get the current frequency of num (default is 0)
            prev_count = count.get(num, 0)
            # If it has been seen before, decrement the frequency count for the old frequency
            if prev_count > 0:
                freq[prev_count] -= 1
                # If the frequency drops to 0, we can remove it
                if freq[prev_count] == 0:
                    del freq[prev_count]
            # Increase the frequency count for this number
            count[num] = prev_count + 1
            new_count = count[num]
            # Update the maximum frequency seen so far
            max_freq = max(max_freq, new_count)
            # Increment the frequency count for the new frequency
            freq[new_count] = freq.get(new_count, 0) + 1

            # Check for the valid cases:
            # Condition 1: All numbers appear once
            if max_freq == 1:
                best = i + 1
            # Condition 2:
            # One frequency is 1 and it appears exactly once, and the other frequencies are all the same (max_freq)
            elif max_freq * freq[max_freq] + 1 == i + 1:
                best = i + 1
            # Condition 3:
            # One number has frequency one more than the others and appears exactly once, 
            # with all the rest having frequency max_freq-1
            elif (max_freq - 1) * (freq.get(max_freq - 1, 0)) + max_freq == i + 1:
                best = i + 1
                
        # Return the maximum valid prefix length
        return best

# Example usage:
# sol = Solution()
# print(sol.maxEqualFreq([2,2,1,1,5,3,3,5]))  # Expected output: 7