Maximum Equal Frequency - Leetcode Solution

The Maximum Equal Frequency problem can be solved using two hash tables. First, we use a hash table to keep track of the frequency count of each number in the array. We then use a second hash table to keep track of the frequency count of each frequency.

We iterate through the entire array, and for each number, we increment its frequency count in the first hash table. We then update the frequency count of its old frequency in the second hash table and increment the frequency count of its new frequency.

We then check if there is only one frequency with frequency count 1. If there is, we return the count of the corresponding number in the first hash table.

If there is no frequency with frequency count 1, we check if there are two different frequencies, one with frequency count 1 and the other with frequency count equal to the size of the array minus 1. If there is, we return the count of the corresponding number in the first hash table.

If neither of the above conditions holds, we check if there is a frequency with frequency count equal to the size of the array. If there is, we return the size of the array.

Otherwise, we iterate through the second hash table and find the maximum frequency count that is less than the size of the array. We then return the count of the corresponding number in the first hash table.

Here is the code implementation of the above solution:

class Solution {
public:
    int maxEqualFreq(vector<int>& nums) {
        unordered_map<int, int> freq;
        unordered_map<int, int> freq_of_freq;
        int max_count = 0;
        int n = nums.size();
        int res = 0;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            int old_freq = freq[num];
            freq[num]++;
            
            // Update frequency of old frequency to handle edge cases
            if (old_freq > 0) {
                freq_of_freq[old_freq]--;
                if (freq_of_freq[old_freq] == 0)
                    freq_of_freq.erase(old_freq);
            }
            freq_of_freq[freq[num]]++;
            
            // Check for edge cases and update res accordingly
            if (freq_of_freq.size() == 1) {
                auto it = freq_of_freq.begin();
                int freq_count = it->first;
                if (freq_count == 1 || freq_count == n)
                    res = i + 1;
                else if (freq_count == n - 1 && it->second == 1)
                    res = i + 1;
            }
            else if (freq_of_freq.size() == 2) {
                auto it = freq_of_freq.begin();
                int freq_count1 = it->first;
                it++;
                int freq_count2 = it->first;
                if ((freq_count1 == 1 && it->second == 1) || (freq_count2 == 1 && it->second == 1) || 
                        (freq_count1 == n - 1 && it->second == 1) || (freq_count2 == n - 1 && it->second == 1))
                    res = i + 1;
            }
            else if (freq_of_freq.size() == 1) {
                auto it = freq_of_freq.begin();
                int freq_count = it->first;
                if (freq_count * freq_of_freq[freq_count] == i || 
                        (freq_count - 1) * (freq_of_freq[freq_count - 1] + 1) == i || 
                        freq_count * (freq_of_freq[freq_count] - 1) == i - freq_count + 1)
                    res = i + 1;
            }
            max_count = max(max_count, freq[num]);
        }
        return res;
    }
};

The time complexity of the above solution is O(N), where N is the size of the array. The space complexity is also O(N) due to the two hash tables.

1