Leetcode 1224: Maximum Equal Frequency

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

Constraints:

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

Problem Analysis:

We need to record the count of numbers and the frequencies. Assume the value of number is a, then c = count[a] is the count of value a, freq[c] is count of different numbers that occurs c times.

We iterate the array from beginning. Assume we iterate the ith number of the array currently, If currently we get m different numbers and m-1 numbers are the same c occurrences. And this prefix subarray is satisfied only if the other one number has occurence:

1. 1 occurence
2. c + 1 occurence

So after we iterate the array, we can get the longest possible length of the prefix array.

Solution

class Solution {
public:
    int maxEqualFreq(vector<int>& nums) {
        vector<int> cnt(100001), freq(100001);
        int res{0};
        for (int i = 1; i <= nums.size(); ++i) {
            int a{nums[i - 1]};
            --freq[cnt[a]];
            int c = ++cnt[a];
            ++freq[cnt[a]];

            if (freq[c] * c == i && i < nums.size()) res = i + 1;
            int d{i - freq[c] * c};
            if ((d == c + 1 || d == 1) && freq[d] == 1)
                res = i;
        }
        
        return res;
    }
};

Time complexity is O(n)

Space complexity is O(K), K = 10⁵