# 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

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

# Solution

Approach 1: maintain counts of counts. Time: O(N).

# Code (Python)

Approach 1:

from collections import defaultdict
class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        result = 0
        # e.g. for [2,2,1,1,5], counts = {2:2, 1:2, 5:1}
        counts = defaultdict(int)
        # e.g. counts_freq = {2:2, 1:1}
        counts_freq = defaultdict(int)
        # e.g. max_freq = 2 for numbers 1 and 2 appearing twice
        max_freq = 0
        for i, num in enumerate(nums):
            # increment count
            counts[num] += 1
            # bump frequency of counts from seen-1 to seen times
            counts_freq[counts[num]] += 1
            counts_freq[counts[num]-1] -= 1
            max_freq = max(max_freq, counts[num])
            # 3 ways to make it
            # 1. everything appears once only
            if (max_freq == 1 
                # 2. everything appears multiple times except for one number appearing once
                or counts_freq[max_freq] * max_freq + 1 == i + 1
                # 3. everything appears multiple times plus one number appears 1 more times than them
                or counts_freq[max_freq-1] * (max_freq - 1) + max_freq == i + 1):
                result = i + 1
        
        return result

# Code (C++)

Approach 1:

Approach 2: