Leetcode 1224: Maximum Equal Frequency

https://leetcode.com/problems/maximum-equal-frequency/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.

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

Example 3:

Input: nums = [1,1,1,2,2,2]
Output: 5

Example 4:

Input: nums = [10,2,8,9,3,8,1,5,2,3,7,6]
Output: 8

Constraints:

• 2 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

Notes:

This question is labeled as a hard question, but its algorithm is quick straightforward. The most difficult part is that it has so many corner cases.

Let us look at the algorithm:

First we will use one hash table to count the frequency of each elements; then we need a second has table to count the frequency of the frequencies.

Now we need figure out what results are the valid ones.

If the size of the second hash table is 1: 

(1) for example, [1, 2, 3, 4, 5], there is only 1 frequency, and mp[1] = 5. In this case, we need the val of the mp[key] is (i+1); where i the index where we scan at;

(2) for example, [1, 1, 1, 1, 1], there is only 1 frequency, and mp[5] = 1. In this case, we need the val ==1, and the key == (i + 1).

(3) otherwise, it cannot be valid

If the size of the second hash table is 2:

(1) If is easy to see that, there must be at least one frequency is 1;

(2) if both are 1, there are two situations:

         (a)  [1, 2, 2, 2], in this case, mp[1] == 1, and mp[3] == 1, and it is valid. So we need min(key) == 1;
         (b) [1, 1, 2, 2, 2], mp[2] ==1, and mp[3] == 1, and it is also valid. So we need abs(key1 - key2) == 1;

(3) if only one of them is 1:

there are two cases:
         
        (a) the key of the 1 value is 1 (then it can be removed); so key1 == 1

        (b) the key of the 1 value is larger than the other key by 1 (the the first key can be removed by 1); so key1 - key2 == 1.

If the size of the second hash table is larger than 2, there is no valid case.

See the code below:

class Solution {
public:
    int maxEqualFreq(vector<int>& nums) {
        int res = 0, len = nums.size();
        if(!len) return res;
        ++res;
        unordered_map<int, int> mp;
        unordered_map<int, int> mp1;
        for(int i=0; i<nums.size(); ++i) {
            int t = nums[i];
            if(mp1.count(mp[t])) {
                --mp1[mp[t]];
                if(mp1[mp[t]] == 0) mp1.erase(mp[t]);
            }
            ++mp[t];
            ++mp1[mp[t]];
            if(mp1.size() == 2) {
                auto it = mp1.begin();
                int k1 = it->first, k2 = next(it, 1)->first;
                int v1 = it->second, v2 = next(it, 1)->second;
                if(v1 != 1 && v2 != 1) continue;//one of them has to be 1; or both 1;
                if(v1 == 1 && v2 == 1) {//both are 1's;
                    if(min(k1, k2) == 1 || abs(k1-k2) == 1) res = i + 1;
                }
                else {//one is 1;
                    if(v1 != 1) {//set v1 is 1 if it is not;
                        swap(k1, k2);
                        swap(v1, v2);
                    }
                    if(k1 == 1 || k1 - k2 == 1) res = i + 1;
                }
            }
            else if(mp1.size() == 1 && (mp1.begin()->first == i + 1 || mp1.begin()->second == i + 1)) res = i + 1;
          //two special cases:  [1, 1, 1, 1, 1], and [1, 2, 3, 4, 5]
        }
        return res;
    }
};