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

Difficulty: interview

Starter code:

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
    def isvalid(self,C):
        if len(C)>2:
            return False
        if len(C)==1:
            a = min(C)
            if a==1 or C[a]==1:
                # EXPLANATION:
                #   a==1   : All lengths are unitary like A=[1,2,3,4,...], so poping anything is fine
                #   C[a]==1: We have a unique length occurence like A=[4,4,4,4,...], so poping anything is fine too
                return True
            # EXPLANATION:
            #     For all other cases of len(C)==1, we'd end with a mistmatch like [1,1,2,2,2], or [1,1,1], so we need to \"return False\" right away
            return False
        #
        # --------- len(D)==2 --------------
        #
        a,b = sorted(C)
        # -> Attempt removing from \"a\"
        if a==C[a]==1: 
            # EXPLANATION:
            #   If we remove from a chain of length \"a\", we will create something smaller than \"b\", so...
            #       The only way to be fine is to have a single element, like [1,2,2,2,3,3,3,...]
            #           -> If we had anything else, we would be stuck with a contradiction (so we move forward to removing \"b\")
            return True
        # -> Attempt removing from \"b\"
        # EXPLANATION:
        #     This only works if there is a single chain of length \"b\", and poping one element makes a chain of length \"a\".
        #     In other words, if works when \"C[b]==1 and (b-1)==a\"
        return True if ( C[b]==1 and (b-1)==a ) else False
    def remove(self,B,x):
        if B[x]==1:
            B.pop(x)
        else:
            B[x] -= 1
    def maxEqualFreq(self, A):
        remove = self.remove
        B = Counter(A)          # Count number of repetitions/length (per value) [1,1,2,2,3,3,4] = {1:2, 2:2, 3:2, 4:1}
        C = Counter(B.values()) # Count number of times a length has been seen   [1,1,2,2,3,3,4] = { 1:1, 2:3 }
        #
        # -> Iterate Reversed, to get best answer at the first match
        for i in reversed(range(len(A))):
            # -> Check if C_dictionary is a valid answer
            if self.isvalid(C):
                return i+1
            #
            # -> Remove current element \"x\" from our System
            x    = A[i]
            # B[x] =  N_repetitions for \"x\"
            #
            remove(C,B[x]) # Deregister old N_repetitions
            remove(B,  x ) # Deregister one instance of \"x\" (from N_repetitions)
            if B[x]:
                # -> If N_repetitions>0 exists, register shortened length
                C[B[x]] += 1
        return 0

class Solution:
    def maxEqualFreq(self, A: List[int]) -> int:
        n = len(A)
        count = collections.defaultdict(int)
        freq = collections.defaultdict(int)
        for i in range(n):
            count[A[i]] +=1
            freq[count[A[i]]]+=1
        
        for i in range(n-1, 0, -1):
            # If include A[i]
            if count[A[i]] * freq[count[A[i]]] == i:
                return i + 1
            freq[count[A[i]]] -= 1
            count[A[i]] -= 1
            if count[A[i-1]] * freq[count[A[i-1]]] == i:
                return i + 1
            
        return 1
            
        


class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        count = collections.defaultdict(int)
        freq = collections.defaultdict(int)

        for n in nums:
            count[n] += 1
            freq[count[n]] += 1

        for i in range(len(nums)-1, 0, -1):
            # 2 case, case 1 , keep i, then you have to remove another on from 0 -- i-1
            if count[nums[i]] * freq[count[nums[i]]] == i:
                return i+1
            freq[count[nums[i]]] -= 1
            count[nums[i]] -= 1

            if count[nums[i-1]] * freq[count[nums[i-1]]] == i:
                return i+1


        return 1




class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        counts = collections.defaultdict(int)
        freq = collections.defaultdict(int)
        res = 0
        for i in range(len(nums)):
            counts[nums[i]] += 1
            freq[counts[nums[i]]] += 1
            count = counts[nums[i]] * freq[counts[nums[i]]]
            if count == i + 1 and i != len(nums) - 1:
                res = max(res,i + 2)
                
            if count == i:
                res = max(res,i + 1)
        return res

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        counts = collections.defaultdict(int)
        freq = collections.defaultdict(int)
        res = 0
        for i in range(len(nums)):
            counts[nums[i]] += 1
            freq[counts[nums[i]]] += 1
            count = counts[nums[i]] * freq[counts[nums[i]]]
            if count == i + 1 and i != len(nums) - 1:
                res = max(res,i + 2)
            if count == i:
                res = max(res,i + 1)
        return res

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        counts = collections.defaultdict(int)
        freq = collections.defaultdict(int)
        res = 0
        for i in range(len(nums)):
            counts[nums[i]] += 1
            freq[counts[nums[i]]] += 1
            
            count = counts[nums[i]] * freq[counts[nums[i]]]
            if count == i + 1 and i != len(nums) - 1:
                res = max(res,i + 2)
                
            if count == i:
                res = max(res,i + 1)
        return res


class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        counts = collections.defaultdict(int)
        freq = collections.defaultdict(int)
        res = 0
        for i in range(len(nums)):
            counts[nums[i]] += 1
            freq[counts[nums[i]]] += 1
            
            count = counts[nums[i]] * freq[counts[nums[i]]]
            if count == i + 1 and i != len(nums) - 1:
                res = max(res,i + 2)
            elif count == i:
                res = max(res,i + 1)
        return res


from collections import Counter, defaultdict

class Solution:
  def maxEqualFreq(self, nums: List[int]) -> int:
    counter = Counter(nums)
    # d: count -> values has such counts
    d = defaultdict(set)
    for x in counter:
      d[counter[x]].add(x)
    # O(n), reverse go through nums updating count of counts
    i = len(nums)
    while d:
      if len(d) == 1:
        k = list(d.keys())[0]
        if k == 1 or len(d[k]) == 1:
          return i
      if len(d) == 2:
        y, z = sorted(d.keys())
        if (y == 1 and len(d[y]) == 1) or (y + 1 == z and len(d[z]) == 1):
          return i
      i -= 1
      # update counter and count of counts
      x = nums[i]
      d[counter[x]].remove(x)
      if not d[counter[x]]:
        d.pop(counter[x])
      counter[x] -= 1
      if counter[x] > 0:
        d[counter[x]].add(x)
    return 0

from collections import Counter, defaultdict

class Solution:
  def maxEqualFreq(self, nums: List[int]) -> int:
    counter = Counter(nums)
    # d: count -> values has such counts
    d = defaultdict(set)
    for x in counter:
      d[counter[x]].add(x)
    # O(n), reverse go through nums updating count of counts
    n = len(nums)
    while d:
      if len(d) == 1:
        k = list(d.keys())[0]
        if k == 1 or len(d[k]) == 1:
          return n
      if len(d) == 2:
        y, z = sorted(d.keys())
        if (y == 1 and len(d[y]) == 1) or (y + 1 == z and len(d[z]) == 1):
          return n
      n -= 1
      # update counter and count of counts
      x = nums[n]
      d[counter[x]].remove(x)
      if not d[counter[x]]:
        d.pop(counter[x])
      counter[x] -= 1
      if counter[x] > 0:
        d[counter[x]].add(x)
    return 0


class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        num_freq = {}
        freq_freq = {}
        for num in nums:
            num_freq[num] = num_freq.get(num, 0) + 1
        for f in num_freq.values():
            freq_freq[f] = freq_freq.get(f, 0) + 1
        
        n = len(nums)
        if len(freq_freq) == 2:
            key1, key2 = list(freq_freq.keys())
            if freq_freq[key1] == 1 and (key1 == 1 or key1 == key2 + 1):
                return n
            if freq_freq[key2] == 1 and (key2 == 1 or key2 == key1 + 1):
                return n
        if len(freq_freq) == 1:
            key = list(freq_freq.keys())[0]
            if key == 1 or freq_freq[key] == 1:
                return n
        
        for i in range(n):
            num = nums[n - i - 1]
            prev_freq = num_freq[num]
            num_freq[num] -= 1
            freq_freq[prev_freq] -= 1
            if freq_freq[prev_freq] == 0:
                del freq_freq[prev_freq]
            if num_freq[num] != 0:
                freq_freq[num_freq[num]] = freq_freq.get(num_freq[num], 0) + 1
            if len(freq_freq) == 2:
                key1, key2 = list(freq_freq.keys())
                if freq_freq[key1] == 1 and (key1 == 1 or key1 == key2 + 1):
                    return n - i - 1
                if freq_freq[key2] == 1 and (key2 == 1 or key2 == key1 + 1):
                    return n - i - 1
            if len(freq_freq) == 1:
                key = list(freq_freq.keys())[0]
                if key == 1 or freq_freq[key] == 1:
                    return n - i - 1
        return 0

from collections import defaultdict
class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        if not nums:
            return 0
        ans = 0
        max_f = 0
        counter, freq_counter = defaultdict(int), defaultdict(int)
        for idx, val in enumerate(nums):
            counter[val] += 1
            max_f = max(max_f, counter[val])
            freq_counter[counter[val]-1] -= 1
            freq_counter[counter[val]] += 1
            if max_f == 1 or max_f * freq_counter[max_f] == idx or ((max_f-1) * (freq_counter[max_f-1] + 1)) == idx:
                ans = max(ans, idx+1)
        return ans

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        from collections import defaultdict
        freq = defaultdict(int)
        count = defaultdict(int)
        res = 0
        for i, n in enumerate(nums, 1):
            freq[count[n]] -= 1
            freq[count[n] + 1] += 1
            count[n] += 1
            
            if freq[count[n]] * count[n] == i and i < len(nums):
                res = i + 1
            
            d = i - freq[count[n]] * count[n]
            if d in [1, count[n]+1] and freq[d] == 1:
                res = i
        return res
            
        
        


class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        counts = collections.Counter()
        freq = collections.Counter()
        res = 0
        
        for i in range(len(nums)):
            counts[nums[i]] += 1
            freq[counts[nums[i]]] += 1
            count = counts[nums[i]] * freq[counts[nums[i]]]
            if count == i + 1 and i != len(nums) - 1:
                res = max(res,i + 2)
            elif count == i:
                res = max(res,i + 1)
        return res

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        counts, freq = collections.Counter(), collections.Counter()
        
        res = 0
        for i, num in enumerate(nums):
            counts[num] += 1
            freq[counts[num]] += 1
            
            count = freq[counts[num]] * counts[num]
            
            if count == i + 1 and i != len(nums) - 1:
                res = max(res, i + 2)
            elif count == i:
                res = max(res, i + 1)

        return res


class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        freq_count, count, res, maxf = defaultdict(int), defaultdict(int), 0, 0
        
        for i, a in enumerate(nums):
            count[a] += 1
            freq_count[count[a]-1] -= 1
            freq_count[count[a]] += 1
            maxf = max(maxf, count[a])
            if maxf==1 or maxf*freq_count[maxf]+1==i+1 or (maxf-1)*freq_count[maxf-1]+maxf==i+1:
                res = i+1
        
        return res

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        count = collections.Counter()
        freq = [0 for _ in range(len(nums) + 1)]
        res = 0
        for n, a in enumerate(nums, 1):
            freq[count[a]] -= 1
            freq[count[a] + 1] += 1
            c = count[a] = count[a] + 1
            if freq[c] * c == n and n < len(nums):
                res = n + 1
            d = n - freq[c] * c
            if d in [c + 1, 1] and freq[d] == 1:
                res = n
        return res

from collections import defaultdict
class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        n = len(nums)
        elemfreq = defaultdict(int)
        freqcnt = defaultdict(int)
        
        i = 0
        n_distinct = 0
        maxfreq = 0
        
        maxprefix = None
        
        
        
        while i != n:
            x = nums[i]
            
            if elemfreq[x] == 0:
                n_distinct += 1
                elemfreq[x] += 1
                freqcnt[1] += 1
            else:
                freqcnt[elemfreq[x]] -= 1
                freqcnt[elemfreq[x]+1] += 1
                elemfreq[x] += 1
            
            maxfreq = max(maxfreq, elemfreq[x])
            
            if maxfreq == 1:
                maxprefix = i
            elif (freqcnt[1] == 1) and (freqcnt[maxfreq] == n_distinct-1):
                maxprefix = i
            elif (freqcnt[maxfreq] == 1) and (freqcnt[maxfreq-1] == n_distinct-1):
                maxprefix = i
            
            i += 1
            
        return maxprefix+1

class Solution:
    def maxEqualFreq(self, nums) -> int:
        res = maxFrq = 0
        count = defaultdict(int)
        freq = defaultdict(int)
        for i, num in enumerate(nums):
            cnt = count[num]
            freq[cnt] -= 1
            
            cnt += 1
            count[num] = cnt

            freq[cnt] += 1
            maxFrq = max(maxFrq, cnt)
            if (maxFrq == 1) or (maxFrq*freq[maxFrq]) == i or ((maxFrq-1)*(freq[maxFrq-1] + 1)) == i:
                res = i + 1
        return res



class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        countMap, freqMap, maxFreq, maxIndex = defaultdict(int), defaultdict(int), 0, 0
        
        for index, x in enumerate(nums):
            freqMap[countMap[x]] -= 1
            countMap[x] += 1
            freqMap[countMap[x]] += 1
            
            maxFreq = max(maxFreq, countMap[x])
            
            if maxFreq*freqMap[maxFreq] == index or (maxFreq-1)*(freqMap[maxFreq-1]+1) == index or maxFreq == 1: 
                maxIndex = index+1
                
        return maxIndex
            


class Solution:     
    def maxEqualFreq(self, A):
        count = collections.Counter()
        freq = [0 for _ in range(len(A) + 1)]
        res = 0
        for n, a in enumerate(A, 1):
            freq[count[a]]-=1
            freq[count[a]+1]+=1
            c = count[a]=count[a]+1
            if freq[c]*c==n and n<len(A):
                res = n+1
            d = n-freq[c]*c
            if d in [c+1,1] and freq[d]==1:
                res = n
        return res

            



from collections import Counter

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        dic = Counter(nums)
        dicdic = Counter(list(dic.values()))
        if len(nums) == 2:
            return 2
        
        while True:
            if len(dicdic) == 1 and (min(dicdic) == 1 or min(dicdic.values()) == 1):
                return len(nums)                
            if len(dicdic) == 2:
                max_dicdic_keys = max(dicdic)
                min_dicdic_keys = min(dicdic)
                if  max_dicdic_keys - min_dicdic_keys == 1 and dicdic[max_dicdic_keys] == 1:
                    return len(nums)
                if min_dicdic_keys == 1 and dicdic[min_dicdic_keys] == 1:
                    return len(nums)
            cleanup = nums.pop()
            if dic[cleanup] - 1 == 0:
                del dic[cleanup]
            else:
                dic[cleanup] = dic[cleanup] -1
            dicdic = Counter(list(dic.values()))
        
        return


class Solution:
    def maxEqualFreq(self, nums) -> int:
        res = maxFrq = 0
        count = defaultdict(int)
        freq = defaultdict(int)
        for i, num in enumerate(nums):
            cnt = count[num]
            freq[cnt] -= 1
            count[num] += 1
            freq[cnt+1] += 1
            
            maxFrq = max(maxFrq, cnt+1)
            if (maxFrq == 1) or (maxFrq*freq[maxFrq]) == i or ((maxFrq-1)*(freq[maxFrq-1] + 1)) == i:
                res = i + 1
        return res



class Solution:

        
    def maxEqualFreq(self, A):
        count = collections.Counter()
        freq = [0 for _ in range(len(A) + 1)]
        res = 0
        for n, a in enumerate(A, 1):
            freq[count[a]] -= 1
            freq[count[a] + 1] += 1
            c = count[a] = count[a] + 1
            if freq[c] * c == n and n < len(A):
                res = n + 1
            d = n - freq[c] * c
            if d in [c + 1, 1] and freq[d] == 1:
                res = n
        return res
            



from collections import defaultdict
class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        counter, freq = defaultdict(int), defaultdict(int)
        max_f = 0
        ans = 0
        for idx, num in enumerate(nums):
            counter[num] += 1
            freq[counter[num]-1] -= 1
            freq[counter[num]] += 1
            max_f = max(max_f, counter[num])
            if freq[max_f] * max_f == idx or max_f == 1 or (max_f-1)*(freq[max_f-1] + 1) == idx:
                ans = idx+1
        return ans

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        counts = collections.Counter()
        freq = collections.Counter()
        res = 0
        for i,num in enumerate(nums):
            counts[num] += 1
            freq[counts[num]] += 1
            
            count = freq[counts[num]] * counts[num]
            if count == i + 1 and i != len(nums) - 1:
                res = max(res,i + 2)
            elif count == i:
                res = max(res,i + 1)
                
        return res

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        cnt, freq = collections.defaultdict(int), collections.defaultdict(int)
        maxF, res = 0, 0
        for i, num in enumerate(nums):
            cnt[num] += 1
            freq[cnt[num]-1] -= 1
            freq[cnt[num]] += 1
            maxF = max(maxF, cnt[num])
            if maxF * freq[maxF] == i or (maxF-1) * (freq[maxF-1]+1) == i or maxF == 1:
                res = i + 1
        return res

class Solution:
    def maxEqualFreq(self, A: List[int]) -> int:
        count = collections.Counter()
        freq = [0 for _ in range(len(A) + 1)]
        res = 0

        for n, a in enumerate(A, 1):
            freq[count[a]] -= 1
            freq[count[a] + 1] += 1
            c = count[a] = count[a] + 1
            if freq[c] * c == n and n < len(A):
                res = n + 1
            d = n - freq[c] * c
            if d in [c + 1, 1] and freq[d] == 1:
                res = n
        return res

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        counter, pattern = {}, {}
        rtn = 0
        if len(nums) <= 3:
            return len(nums)
        for i in range(len(nums)):
            n = nums[i]
            if n in counter:
                t = counter[n]
                counter[n] += 1
            else:
                t = 0
                counter[n] = 1
                
            if t > 0:
                pattern[t] -= 1
                if pattern[t] == 0:
                    del pattern[t]
                
            if t+1 in pattern:
                pattern[t+1] += 1
            else:
                pattern[t+1] = 1
            if len(pattern) == 1:
                for k, v in list(pattern.items()):
                    if k == 1 or v == 1:
                        rtn = max(rtn, i)
            elif len(pattern) == 2:
                if 1 in pattern and pattern[1] == 1:
                    rtn = max(i, rtn)
                [m1, m2] = [(k,v) for k,v in list(pattern.items())]
                if (m1[0] - m2[0] == 1 and m1[1] == 1) or (m2[0] - m1[0] == 1 and m2[1] == 1):
                    rtn = max(rtn, i)
        return rtn + 1


class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        cnt, freq = collections.defaultdict(int), collections.defaultdict(int)
        maxF, res = 0, 0
        for i,num in enumerate(nums):
            cnt[num] += 1
            freq[cnt[num]-1] -= 1
            freq[cnt[num]] += 1
            maxF = max(maxF,cnt[num])
            if maxF * freq[maxF] == i or (maxF-1) * (freq[maxF-1]+1) == i or maxF == 1:
                res = i + 1
        return res

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        N = len(nums)
        freqCount = [0 for i in range(N+1)]
        umap = dict()
        minFreq = 1
        maxFreq = 1
        umap[nums[0]] = 1
        freqCount[1] = 1
        result = 1
        
        for i in range(1, N):
            if nums[i] not in umap:
                umap[nums[i]] = 1
                minFreq = 1
            else:
                freqCount[umap[nums[i]]] -= 1
                if freqCount[umap[nums[i]]] == 0 and minFreq == umap[nums[i]]:
                    minFreq = umap[nums[i]] + 1
                umap[nums[i]] += 1
            freqCount[umap[nums[i]]] += 1
            
            if umap[nums[i]] > maxFreq:
                maxFreq = umap[nums[i]]
            
            if maxFreq == minFreq+1 and freqCount[maxFreq] == 1:
                result = i+1
            if maxFreq == minFreq and freqCount[maxFreq] == i+1:
                result = i + 1
            if maxFreq == minFreq and freqCount[maxFreq] == 1:
                result = i + 1
            if maxFreq * freqCount[maxFreq] == i:
                result = i + 1
                
        return result


class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        d = Counter(nums)
        #print(d)
        
        for i in reversed(range(len(nums))):
            vlist = list(d.values())
            #print(vlist)
            s = list(set(vlist))
            
            if len(s) == 1:
                if s[0] == 1:
                    return i+1
                if len(vlist) == 1:
                    return i + 1
                
            if len(s) == 2:
                if 1 in s:
                    if vlist.count(1) == 1:
                        return i+1

                maxint = max(s[0],s[1])
                if vlist.count(maxint) == 1 and abs(s[1]-s[0]) == 1:
                    return i+1
            
            if d[nums[i]] == 1:
                d.pop(nums[i])
            else:
                d[nums[i]] -= 1
            
        
        return 1

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        counts = collections.Counter()
        freq = collections.Counter()
        res = 0
        for i in range(len(nums)):
            counts[nums[i]] += 1
            freq[counts[nums[i]]] += 1
            
            count = counts[nums[i]] * freq[counts[nums[i]]]
            if count == i + 1 and i != len(nums) - 1:
                res = max(res,i + 2)
            if count == i:
                res = max(res,i + 1)
        return res

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        freqs = defaultdict(int)
        freqfreq = defaultdict(int)
        
        rec = 0
        
        for i, n in enumerate(nums):
            freqs[n]+= 1
            freqfreq[freqs[n]] +=1
            
            if freqs[n] != 1:
                freqfreq[freqs[n]-1] -=1
                if freqfreq[freqs[n]-1] == 0:
                    del freqfreq[freqs[n]-1]
            
            
            if len(freqfreq)<3:
                if len(freqfreq)==1 and len(freqs)==1:
                    rec = i+1
                elif len(freqfreq)==1 and list(freqfreq.keys())[0]==1:
                    rec = i+1
                elif len(freqfreq)==2:
                    fs = sorted(freqfreq.keys())
                    if fs[0]==1 and freqfreq[fs[0]]==1:
                        rec = i+1
                    elif fs[0]+1 == fs[1] and freqfreq[fs[1]]==1:
                        rec = i+1
        return rec

class Solution:
    def maxEqualFreq(self, nums) -> int:
        res = maxFrq = 0
        count = defaultdict(int)
        freq = defaultdict(int)
        for i in range(len(nums)):
            cnt = count[nums[i]]
            freq[cnt] -= 1
            count[nums[i]] += 1

            cnt = count[nums[i]]
            freq[cnt] += 1
            maxFrq = max(maxFrq, count[nums[i]])
            if (maxFrq == 1) or (maxFrq*freq[maxFrq]) == i or ((maxFrq-1)*(freq[maxFrq-1] + 1)) == i:
                res = i + 1
        return res



class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        if len(nums)==1: return 0
        counts, freq = collections.Counter(), collections.Counter()
        res = 0
        for i, num in enumerate(nums):
            # update counts
            counts[num] += 1
            # update counts with that frequency
            freq[counts[num]] += 1

            count = freq[counts[num]] * counts[num]
            if count == i + 1 and i != len(nums) - 1: # case 1
                res = max(res, i + 2)
            elif count == i: # case 2
                res = max(res, i + 1)
        return res
            
            
            


class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        counter, pattern = {}, {}
        rtn = 0
        if len(nums) <= 3:
            return len(nums)
        for i in range(len(nums)):
            n = nums[i]
            if n in counter:
                t = counter[n]
                counter[n] += 1
            else:
                t = 0
                counter[n] = 1
                
            if t > 0:
                pattern[t] -= 1
                if pattern[t] == 0:
                    del pattern[t]
                
            if t+1 in pattern:
                pattern[t+1] += 1
            else:
                pattern[t+1] = 1
            if len(pattern) == 1:
                for k, v in list(pattern.items()):
                    if k == 1 or v == 1:
                        rtn = max(rtn, i)
            elif len(pattern) == 2:
                for k,v in list(pattern.items()):
                    if k == 1 and v == 1:
                        rtn = max(i, rtn)
                [m1, m2] = [(k,v) for k,v in list(pattern.items())]
                if (m1[0] - m2[0] == 1 and m1[1] == 1) or (m2[0] - m1[0] == 1 and m2[1] == 1):
                    rtn = max(rtn, i)
        return rtn + 1


class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        count = collections.Counter()
        n = len(nums)
        freq = collections.Counter()
        res = 0
        
        for i, a in enumerate(nums, 1):
            if count[a] in freq:
                freq[count[a]] -= 1
            freq[count[a]+1] += 1
            count[a] += 1
            f = count[a]
            if freq[f] * f == i and i < n:
                res = i+1
            else:
                d = i - freq[f]*f
                if d in [1, f+1] and freq[d] == 1:
                    res = i
        return res
            


class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        res = 0
        numToCount = {}
        countToNum = {}
        for i in range(len(nums)):
            num = nums[i]
            if num not in numToCount:
                numToCount[num] = 0
            count = numToCount[num]
            if count != 0:
                countToNum[count].remove(num)
                if len(countToNum[count]) == 0:
                    del countToNum[count]
            count += 1
            if count not in countToNum:
                countToNum[count] = set()
            countToNum[count].add(num)
            numToCount[num] = count
            if len(countToNum) == 1:
                if count == 1 or len(countToNum[count]) == 1:
                    res = i + 1
            elif len(countToNum) == 2:
                keys = sorted(list(countToNum.keys()))
                if (keys[0] == 1 and len(countToNum[keys[0]])) == 1 or (keys[0] + 1 == keys[1] and len(countToNum[keys[1]]) == 1):
                    res = i + 1
            # print(countToNum)
        return res


class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        
        hashtable = {}
        hashcount = {}
        m  =0
        
        for i in range(len(nums)):
            
            if nums[i] not in list(hashtable.keys()):
                hashtable[nums[i]]=1
                if 1 not in list(hashcount.keys()):
                    hashcount[1] = [nums[i]]
                else:
                    hashcount[1].append(nums[i])
            else:
                c = hashtable[nums[i]]
                hashtable[nums[i]]+=1
                
                hashcount[c].remove(nums[i])
                if len(hashcount[c])==0:
                    del hashcount[c]
                if c+1 in list(hashcount.keys()):
                    hashcount[c+1].append(nums[i])
                else:
                    hashcount[c+1]=[nums[i]]
            
            #print(hashcount)
                
            if (len(list(hashtable.keys()))==1):
                m = i+1
                
            else:
                l = list(hashcount.keys())
                
                if (len(l)==1 and l[0]==1):
                    m = max(m,i+1)
                if len(list(hashcount.keys()))==2:
                    if 1 in list(hashcount.keys()) and len(hashcount[1])==1:
                        m = max(m,i+1)
                    if abs(l[0]-l[1])==1 and len(hashcount[max(l[0],l[1])])==1:
                        m = max(m,i+1)
                
        return m
            
            


from collections import Counter
class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        val_occurences = Counter(nums)
        occ_count = Counter([v for k, v in list(val_occurences.items())])
        M = len(nums)
        for i in range(M - 1, -1, -1):
            if len(occ_count) == 2:
                for k, v in list(occ_count.items()):
                    #case where if we reduce we have all the same keys
                    if v == 1 and (k - 1 in occ_count or k - 1 == 0):
                        return i + 1
            elif len(occ_count) == 1:
                if 1 in list(occ_count.keys()) or 1 in list(occ_count.values()):
                    return i + 1

            val = nums[i]
            count = val_occurences[val]
            val_occurences[val]-=1
            if val_occurences[val] == 0:
                del val_occurences[val]
            occ_count[count]-=1
            if occ_count[count] == 0:
                del occ_count[count]
            if count-1 != 0:
                occ_count[count-1]+=1
        return 0


from collections import Counter
class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        counts, freq = Counter(), Counter()
        ans, maxF = 0, 0
        for i, num in enumerate(nums):
            counts[num] += 1
            freq[counts[num] - 1] -= 1
            freq[counts[num]] += 1
            maxF = max(maxF, counts[num])
            if maxF*freq[maxF] == i or (maxF - 1)*(freq[maxF-1] + 1) == i or maxF == 1:
                ans = i + 1
        return ans


class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        freq={}
        num={}
        m=0
        for i in range(len(nums)):
            if nums[i] in num:
                num[nums[i]]+=1
                if((num[nums[i]]) in freq):
                    freq[num[nums[i]]]+=1
                    if((num[nums[i]]-1) in freq):
                        freq[num[nums[i]]-1]-=1
                    if((num[nums[i]]-1) in freq)and(freq[num[nums[i]]-1]==0):
                        freq.pop(num[nums[i]]-1)
                else:
                    freq[num[nums[i]]]=1
                    if((num[nums[i]]-1) in freq):
                        freq[num[nums[i]]-1]-=1
                    if((num[nums[i]]-1) in freq)and(freq[num[nums[i]]-1]==0):
                        freq.pop(num[nums[i]]-1)
            else:
                num[nums[i]]=1
                if 1 in freq:
                    freq[1]+=1
                    if(0 in freq)and(freq[0]==0):
                        freq.pop(0)
                else:
                    freq[1]=1
                    if(0 in freq)and(freq[0]==0):
                        freq.pop(0)
            if(len(freq)==1)and(1 in freq):
                m=i+1
            elif(len(freq)==2):
                a=list(freq.keys())
                b=max(a)
                c=min(a)
                if(b-c==1)and(freq[b]==1):
                    m=i+1
                if(1 in freq)and(freq[1]==1):
                    m=i+1
        if(len(freq)==1)and(len(set(nums))==1):
            return len(nums)
        return m
                


class Solution:
    # O(n) time, O(n) space
    def maxEqualFreq(self, nums: List[int]) -> int:
        count2num = defaultdict(set)
        num_count = Counter()
        max_len = 0
        
        def is_valid(count2num):
            counts = list(count2num.keys())
            # each element appears only once, or there is only 1 kind of element 
            if len(counts) == 1 and (counts[0] == 1 or len(count2num[counts[0]]) == 1):
                return True
            # Otherwise, if there are not 2 different counts, this prefix should be invalid
            if len(counts) != 2:
                return False
            # 2 different counts
            counts.sort()
            # Only 1 element has count 1, and others have a same different count
            if counts[0] == 1 and len(count2num[1]) == 1:
                return True
            # Two consecutive counts, and the larger one only has 1 element
            if counts[0] + 1 == counts[1] and len(count2num[counts[1]]) == 1:
                return True
            
            return False
        
        for i in range(len(nums)):
            num = nums[i]
            num_count[num] += 1
            count = num_count[num]
            count2num[count].add(num)
            if count > 1:
                count2num[count - 1].remove(num)
                if not count2num[count - 1]:
                    count2num.pop(count - 1)
            if is_valid(count2num):
                max_len = max(max_len, i + 1)
        
        return max_len

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        count2num = defaultdict(set)
        num_count = Counter()
        max_len = 0
        
        def is_valid(count2num):
            counts = list(count2num.keys())
            # each element appears only once, or there is only 1 kind of element 
            if len(counts) == 1 and (counts[0] == 1 or len(count2num[counts[0]]) == 1):
                return True
            # Otherwise, if there are not 2 different counts, this prefix should be invalid
            if len(counts) != 2:
                return False
            # 2 different counts
            counts.sort()
            # Only 1 element has count 1, and others have a same different count
            if counts[0] == 1 and len(count2num[1]) == 1:
                return True
            # Two consecutive counts, and the larger one only has 1 element
            if counts[0] + 1 == counts[1] and len(count2num[counts[1]]) == 1:
                return True
            
            return False
        
        for i in range(len(nums)):
            num = nums[i]
            num_count[num] += 1
            count = num_count[num]
            count2num[count].add(num)
            if count > 1:
                count2num[count - 1].remove(num)
                if not count2num[count - 1]:
                    count2num.pop(count - 1)
            if is_valid(count2num):
                max_len = max(max_len, i + 1)
        
        return max_len

class Solution:
    def isvalid(self,D):
        if len(D)>2:
            return False
        if len(D)==1:
            a = min(D)
            if a==1 or D[a]==1:
                # a==1: all lengths are unitary (like [1,2,3,4,...]), so removing anything is fine
                # D[a]==1, we have a unique length occurence (like [4,4,4,4,...]), so...
                #          so we can pop one element and be fine
                return True
            return False
        # len(D)==2 now
        a,b = min(D),max(D)
        if a==D[a]==1: 
            # If we remove from a chain of length \"a\", we will create something smaller than \"b\", so...
            # The only way to be fine is to have a single element, like [1,2,2,2,3,3,3,...]
            #     - If we have more of the smallest length, we're into trouble
            return True
        # Remove from \"b\"
        return True if ( D[b]==1 and (a+1)==b ) else False
    def maxEqualFreq(self, A):
        best = 0
        B = Counter() # Count number of repetitions/length (per value)
        C = Counter() # Count number of times a length has been seen
        for i,x in enumerate(A):
            if B[x]:
                # If we had seen B before, deregister its \"old\" length
                if C[B[x]] == 1:
                    C.pop( B[x] )
                else:
                    C[B[x]] -= 1
            B[x]    += 1 # increase rep. counter
            C[B[x]] += 1 # Register new length seen
            #
            if self.isvalid(C):
                best = i+1
        return best

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        counter = Counter()
        freq_counter = Counter()
        res = 0
        
        for i, num in enumerate(nums):
            if counter[num]:
                freq_counter[counter[num]]-=1
                if not freq_counter[counter[num]]:
                    del freq_counter[counter[num]]
            counter[num] += 1
            freq_counter[counter[num]]+=1
    
            if len(freq_counter)==1:
                for k in freq_counter:
                    if k==1 or freq_counter[k]==1:
                        res = max(res, i+1)
            if len(freq_counter)==2:
                k0, k1 = sorted(freq_counter)
                if freq_counter[1]==1 or k1-k0==1 and freq_counter[k1]==1:
                    res = max(res, i+1)
            # print(i, num, res, freq_counter)
        return res

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        counts, freq = collections.Counter(), collections.Counter()
        res = 0
        for i, num in enumerate(nums):
        
            counts[num] += 1
           
            freq[counts[num]] += 1

            count = freq[counts[num]] * counts[num]
            if count == i + 1 and i != len(nums) - 1: 
                res = max(res, i + 2)
            elif count == i:
                res = max(res, i + 1)
        return res


class Solution:
    def maxEqualFreq(self, A: List[int]) -> int:
        
        # Life is hard especially when you think it's easy.
        # Oh my god!!! Please read the problem again. It needs an array prefix of nums!!! Therefore it should start from the first. Shit!!
        
        
        counter = collections.Counter()
        fre = [0] * (len(A) + 1)
        res = 0
        for n, a in enumerate(A, 1):
            c = counter[a]
            fre[c] -= 1
            fre[c + 1] += 1
            c += 1
            counter[a] += 1
            if c * fre[c] == n and n < len(A):
                res = n + 1
            d = n - c*fre[c]
            if d in [1, c+1] and fre[d] == 1:
                res = n
            
        return res
        
        
#         count = collections.Counter()
#         freq = [0 for _ in range(len(A) + 1)]
#         res = 0
#         for n, a in enumerate(A, 1):
            
#             # the frequence update, since some number appear again, its appearance affect its count and the frequence.
            
#             freq[count[a]] -= 1
#             freq[count[a] + 1] += 1
#             c = count[a] = count[a] + 1
#             if freq[c] * c == n and n < len(A):
#                 res = n + 1
#             d = n - freq[c] * c
#             if d in [c + 1, 1] and freq[d] == 1:
#                 res = n
#         return res


class Solution:
    def maxEqualFreq(self, A: List[int]) -> int:
        n = len(A)
        count = collections.defaultdict(int)
        freq = collections.defaultdict(int)
        for i in range(n):
            count[A[i]] +=1
            freq[count[A[i]]]+=1
        
        print((count, freq))
        for i in range(n-1, 0, -1):
            # If include A[i]
            if count[A[i]] * freq[count[A[i]]] == i:
                return i + 1
            freq[count[A[i]]] -= 1
            count[A[i]] -= 1
            if count[A[i-1]] * freq[count[A[i-1]]] == i:
                return i + 1
            
        return 1
            
        


class Solution:
    def maxEqualFreq(self, A: List[int]) -> int:
        
        # Life is hard especially when you think it's easy.
        # Oh my god!!! Please read the problem again. It needs an array prefix of nums!!! Therefore it should start from the first. Shit!!
        
        
        counter = collections.Counter()
        fre = [0] * (len(A) + 1)
        res = 0
        for n, a in enumerate(A, 1):
            
            fre[counter[a]] -= 1
            fre[counter[a] + 1] += 1
            c = counter[a] = counter[a] + 1
            if c * fre[c] == n and n < len(A):
                res = n + 1
            d = n - c*fre[c]
            if d in [1, c+1] and fre[d] == 1:
                res = n
            
        return res
        
        
#         count = collections.Counter()
#         freq = [0 for _ in range(len(A) + 1)]
#         res = 0
#         for n, a in enumerate(A, 1):
            
#             # the frequence update, since some number appear again, its appearance affect its count and the frequence.
            
#             freq[count[a]] -= 1
#             freq[count[a] + 1] += 1
#             c = count[a] = count[a] + 1
#             if freq[c] * c == n and n < len(A):
#                 res = n + 1
#             d = n - freq[c] * c
#             if d in [c + 1, 1] and freq[d] == 1:
#                 res = n
#         return res


from collections import defaultdict

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        num_to_count = defaultdict(int)
        count_to_distinct_num = defaultdict(int)
        result = 0
        
        
        for i, n in enumerate(nums):
            prev_count = num_to_count[n]
            new_count = prev_count + 1
            num_to_count[n] = new_count
            
            if prev_count > 0:
                count_to_distinct_num[prev_count] -= 1
                
                if count_to_distinct_num[prev_count] == 0:
                    del count_to_distinct_num[prev_count]
                    
            count_to_distinct_num[new_count] += 1
            
            if valid_prefix(count_to_distinct_num, new_count):
                result = i + 1
                
        return result
    
def valid_prefix(count_to_distinct_num, hint):
    assert len(count_to_distinct_num) > 0
    assert 0 not in count_to_distinct_num
    assert hint in count_to_distinct_num
    
    if 1 in count_to_distinct_num:
        if len(count_to_distinct_num) == 1:
            return True
        
        if len(count_to_distinct_num) == 2 and count_to_distinct_num[1] == 1:
            return True
        
    if len(count_to_distinct_num) == 1:
        if count_to_distinct_num[hint] == 1:
            return True
    
    if len(count_to_distinct_num) != 2:
        return False
    
    if hint-1 in count_to_distinct_num:
        return count_to_distinct_num[hint] == 1
    
    if hint+1 in count_to_distinct_num:
        return count_to_distinct_num[hint+1] == 1
    
    return False
                    
            
        


from collections import Counter
class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        res = 1        
        count = defaultdict(int)
        inverseCount = defaultdict(set)
        for i in range(len(nums)):
            if count[nums[i]] in inverseCount:
                inverseCount[count[nums[i]]].remove(nums[i])
                if len(inverseCount[count[nums[i]]]) == 0:
                    inverseCount.pop(count[nums[i]])
            count[nums[i]] += 1
            inverseCount[count[nums[i]]].add(nums[i])

            if self.canBeEqualFreq(inverseCount):
                res = i+1
        
        return res
            
            
    def canBeEqualFreq(self, ic):
        ickeys, icvalues = list(ic.keys()), list(ic.values())
        if len(ic) == 1:
            return len(icvalues[0])==1 or 1 in list(ic.keys())
        
        if len(ic) > 2:
            return False
        # case 1: 1,2,2,2,3,3,3
        if 1 in ickeys and len(ic[1])==1:
            return True
        # case 2: 1,1,2,3
        if (ickeys[0] - ickeys[1] == 1 and len(ic[ickeys[0]])==1) or (ickeys[1] - ickeys[0] == 1 and len(ic[ickeys[1]])==1) :
            return True
        
        return False


class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        freq = collections.Counter()
        counts = collections.Counter()
        res = 0
        for i, val in enumerate(nums):
            save = freq[val]
            if save:
                counts[save] -= 1
                if not counts[save]:
                    del counts[save]
            freq[val] += 1
            counts[freq[val]] += 1
            if len(counts) == 1 and (counts[1] > 0 or len(freq) == 1):
                res = i + 1
            if len(counts) == 2:
                (a, b) = list(counts.keys())
                if abs(a - b) == 1 and counts[max(a, b)] == 1:
                    res = i + 1
                if counts[1] == 1:
                    res = i + 1
            # print(freq, counts)
        return res


class Solution:
    def isvalid(self,D):
        if len(D)>2:
            return False
        if len(D)==1:
            a = min(D)
            if a==1 or D[a]==1:
                # a==1: all lengths are unitary (like [1,2,3,4,...]), so removing anything is fine
                # D[a]==1, we have a unique length occurence (like [4,4,4,4,...]), so...
                #          so we can pop one element and be fine
                return True
            return False
        # len(D)==2 now
        a,b = min(D),max(D)
        if a==D[a]==1:
            return True
        return True if (a==(b-1) and D[b]==1) else False
    def maxEqualFreq(self, A):
        best = 0
        B = Counter() # Count number of repetitions/length (per value)
        C = Counter() # Count number of times a length has been seen
        for i,x in enumerate(A):
            if B[x]:
                # If we had seen B before, deregister its \"old\" length
                if C[B[x]] == 1:
                    C.pop( B[x] )
                else:
                    C[B[x]] -= 1
            B[x]    += 1 # increase rep. counter
            C[B[x]] += 1 # Register new length seen
            #
            if self.isvalid(C):
                best = i+1
        return best

class Solution:
    def maxEqualFreq(self, A: List[int]) -> int:
        
        
        count = collections.Counter()
        freq = [0 for _ in range(len(A) + 1)]
        res = 0
        for n, a in enumerate(A, 1):
            freq[count[a]] -= 1
            freq[count[a] + 1] += 1
            c = count[a] = count[a] + 1
            if freq[c] * c == n and n < len(A):
                res = n + 1
            d = n - freq[c] * c
            if d in [c + 1, 1] and freq[d] == 1:
                res = n
        return res

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        cnt,freq,maxF,res = collections.defaultdict(int), collections.defaultdict(int),0,0
        for i,num in enumerate(nums):
            cnt[num] += 1
            freq[cnt[num]-1] -= 1
            freq[cnt[num]] += 1
            maxF = max(maxF,cnt[num])
            if maxF*freq[maxF] == i or (maxF-1)*(freq[maxF-1]+1) == i or maxF == 1:
                res = i + 1
        return res


class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        counts = collections.Counter()
        freq = collections.Counter()
        res = 0
        for i,num in enumerate(nums):
            counts[num] += 1
            freq[counts[num]] += 1
            
            count = freq[counts[num]] * counts[num]
            if count == i + 1 and i != len(nums) - 1:
                res = max(res,i + 2)
            elif count == i:
                res = max(res,i + 1)
        return res


class Solution:
    def isvalid(self,D):
        if len(D)==1:
            a = min(D)
            if a==1 or D[a]==1:
                # a==1: all lengths are unitary (like [1,2,3,4,...]), so removing anything is fine
                # D[a]==1, we have a unique length occurence (like [4,4,4,4,...]), so...
                #          so we can pop one element and be fine
                return True
            return False
        # len(D)==2 now
        a,b = min(D),max(D)
        if a==D[a]==1: 
            # If we remove from a chain of length \"a\", we will create something smaller than \"b\", so...
            # The only way to be fine is to have a single element, like [1,2,2,2,3,3,3,...]
            #     - If we have more of the smallest length, we're into trouble
            return True
        # Remove from \"b\"
        return True if ( D[b]==1 and (a+1)==b ) else False
    def maxEqualFreq(self, A):
        best = 0
        B = Counter() # Count number of repetitions/length (per value)
        C = Counter() # Count number of times a length has been seen
        for i,x in enumerate(A):
            old = B[x]
            if old:
                if C[old]==1:
                    C.pop(old)
                else:
                    C[old] -= 1
            B[x]    += 1 # increase rep. counter
            C[B[x]] += 1 # Register new length seen
            #
            if len(C)<=2 and self.isvalid(C):
                best = i+1
        return best


class Solution:
    def maxEqualFreq(self, nums) -> int:
        '''

        :param nums: : List[int]
        :return:
        '''

        n = len(nums)
        a= Counter(nums)

        # print(nums)
        for i in range(n-1,0,-1):
            if len(a) == 1:
                p = [i for i in list(a.keys())][0]
                return a[p]
            b = Counter(list(a.values()))

            if len(b) > 2:
                a[nums[i]] -= 1
                if not a[nums[i]]:
                     a.pop(nums[i])
                continue
            elif len(b) == 1:
                if 1 in list(a.values()):
                    return i+1
                return i
            elif len(b) == 2:
                if 1 in list(b.keys()) and b[1]==1:
                    return i+1
                if 1 in list(b.values()):
                    mia,aa =[la for la in list(b.keys())]
                    mia,aa = min(mia,aa),max(mia,aa)
                    if b[aa]==1 and aa-mia ==1 :
                        return i+1
                    a[nums[i]] -= 1
                    if not a[nums[i]]:
                        a.pop(nums[i])
                else:
                    a[nums[i]] -= 1
                    if not a[nums[i]]:
                        a.pop(nums[i])
                    continue



class LinkedList:
    def __init__(self):
        self.map = {}
        self.min = -1
        self.max = -1
    def add_to_key(self, key):
        if key in self.map:
            self.map[key][0] += 1
            new_key = self.map[key][1]
            while new_key >= 1 and self.map[key][0] > self.map[new_key][0]:
                self.map[key][1], self.map[new_key][1] = self.map[new_key][1], key
                self.map[new_key][2], self.map[key][2] = self.map[key][2], new_key
                if self.map[new_key][2] > 0:
                    self.map[self.map[new_key][2]][1] = new_key

                
                # update min
                if self.min == key:
                    self.min = new_key
                new_key = self.map[key][1]
            if new_key >= 1:
                self.map[new_key][2] = key
        else:
            self.map[key] = [1, self.min, -1]
            if self.min > 0:
                self.map[self.min][2] = key
            # update min
            self.min = key
        # update max
        if self.max <= 0 or self.map[self.max][0] < self.map[key][0]:
            self.max = key
        
    def check(self):
        A = self.biggest()
        B = self.smallest()
        if A == 1:
            return True
        elif B == 1:
            C = self.unique_min()
            if not C:
                if A == 2 and self.unique_max():
                    return True
                else:
                    return False
            else:
                next_min = self.map[self.min][1]
                if self.map[next_min][0] == A:
                    return True
                else:
                    return False
        else:
            D = self.unique_max()
            if D:
                return A == B + 1 or A == B
            else:
                return False
            
    def smallest(self):
        if self.min == -1:
            return 0
        else:
            return self.map[self.min][0]
    def biggest(self):
        if self.max == -1:
            return 0
        else:
            return self.map[self.max][0]
    def unique_min(self):
        if self.min <= 0:
            return True
        else:
            next_min = self.map[self.min][1]
            return next_min >= 1 and self.map[self.min][0] != self.map[next_min][0]
    def unique_max(self):
        if self.max <= 0:
            return True
        else:
            next_max = self.map[self.max][2]
            if next_max > 0:
                return self.map[self.max][0] != self.map[next_max][0]
            else:
                return True
        
class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        out = LinkedList()
        result = 2
        for length, num in enumerate(nums):
            out.add_to_key(num)
            #print(length + 1, out.check(), out.map, out.max, out.min, out.unique_max())
            #xx = [str(length)]
            #elem = out.max
            #limit = 100
            #while elem != -1 and limit > 0:
            #    xx.append(str(elem))
            #    elem = out.map[elem][2]
            #    limit -= 1
            #print(\">\".join(xx))
            if out.check():
                result = length + 1
        return result
        


class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        counterCounter = defaultdict(int)
        numCounter = defaultdict(int)
        ans = 0
        maxRepeat = 0
        for i, num in enumerate(nums):
            numCounter[num] += 1
            counterCounter[numCounter[num]] += 1
            maxRepeat = max(numCounter[num], maxRepeat)
            if numCounter[num] > 1:
                counterCounter[numCounter[num]-1] -= 1
            if (counterCounter[maxRepeat] == 1 and (maxRepeat-1)*(counterCounter[maxRepeat-1]+1) == i) or (counterCounter[1] == 1 and (maxRepeat)*(counterCounter[maxRepeat]) == i):
                ans = i+1
            if maxRepeat == 1 or maxRepeat == i+1:
                ans = i+1 
            
            # print(counterCounter, maxRepeat)
        return ans

from collections import defaultdict
class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        if not nums:
            return 0
        counter, freq = defaultdict(int), defaultdict(int)
        max_f, ans = 0, 0
        for idx, num in enumerate(nums):
            counter[num] += 1
            max_f = max(max_f, counter[num])
            freq[counter[num]-1] -= 1
            freq[counter[num]] += 1
            if max_f == 1 or max_f * freq[max_f] == idx or (max_f-1) * (freq[max_f-1] + 1) == idx:
                ans = idx + 1
        return ans


class Solution:
    def isvalid(self,D):
        if len(D)==1:
            a = min(D)
            if a==1 or D[a]==1:
                # a==1: all lengths are unitary (like [1,2,3,4,...]), so removing anything is fine
                # D[a]==1, we have a unique length occurence (like [4,4,4,4,...]), so...
                #          so we can pop one element and be fine
                return True
            return False
        # len(D)==2 now
        a,b = min(D),max(D)
        if a==D[a]==1: 
            # If we remove from a chain of length \"a\", we will create something smaller than \"b\", so...
            # The only way to be fine is to have a single element, like [1,2,2,2,3,3,3,...]
            #     - If we have more of the smallest length, we're into trouble
            return True
        # Remove from \"b\"
        return True if ( D[b]==1 and (a+1)==b ) else False
    def maxEqualFreq(self, A):
        best = 0
        B = Counter() # Count number of repetitions/length (per value)
        C = Counter() # Count number of times a length has been seen
        for i,x in enumerate(A):
            old = B[x]
            if old:
                if C[old]==1:
                    C.pop(old)
                else:
                    C[old] -= 1
            B[x]     += 1 # increase rep. counter
            C[old+1] += 1 # Register new length seen
            #
            if len(C)<3 and self.isvalid(C):
                best = i+1
        return best

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        r = 0
        c = collections.Counter()
        countToNums = collections.Counter()
        high = 0
        unique = 0
        
        for i in range(len(nums)):
            if not c[nums[i]]:
                unique += 1
            
            countToNums[c[nums[i]]] -= 1
            c[nums[i]] += 1
            countToNums[c[nums[i]]] += 1
            if c[nums[i]] > high:
                high = c[nums[i]]
                
            if countToNums[high] == 1 and countToNums[high-1] == unique-1 or countToNums[1] == 1 and countToNums[high] == unique-1 or high == 1:
                r = i+1
                
        return r
            


class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        r = 1
        c = collections.Counter()
        countToNums = collections.Counter()
        high = 0
        unique = 0
        
        for i in range(len(nums)):
            if not c[nums[i]]:
                unique += 1
            
            countToNums[c[nums[i]]] -= 1
            c[nums[i]] += 1
            countToNums[c[nums[i]]] += 1
            if c[nums[i]] > high:
                high = c[nums[i]]
                
            if countToNums[high] == 1 and countToNums[high-1] == unique-1 or countToNums[1] == 1 and countToNums[high] == unique-1 or countToNums[1] == unique:
                r = i+1
                
        return r
            


class Solution:
    def isvalid(self,D):
        if len(D)>2:
            return False
        if len(D)==1:
            a = min(D)
            if a==1 or D[a]==1:
                return True
            return False
        # len(D)==2 now
        a,b = min(D),max(D)
        if a==D[a]==1:
            return True
        return True if (a==(b-1) and D[b]==1) else False
    def maxEqualFreq(self, A):
        best = 0
        B = Counter() # Count number of repetitions/length (per value)
        C = Counter() # Count number of times a length has been seen
        for i,x in enumerate(A):
            if B[x]:
                # If we had seen B before, deregister its \"old\" length
                if C[B[x]] == 1:
                    C.pop( B[x] )
                else:
                    C[B[x]] -= 1
            B[x]    += 1 # increase rep. counter
            C[B[x]] += 1 # Register new length seen
            #
            if self.isvalid(C):
                best = i+1
        return best

class Solution:
    def isvalid(self,D):
        if len(D)==1:
            a = min(D)
            if a==1 or D[a]==1:
                # a==1: all lengths are unitary (like [1,2,3,4,...]), so removing anything is fine
                # D[a]==1, we have a unique length occurence (like [4,4,4,4,...]), so...
                #          so we can pop one element and be fine
                return True
            return False
        # len(D)==2 now
        a,b = min(D),max(D)
        if a==D[a]==1: 
            # If we remove from a chain of length \"a\", we will create something smaller than \"b\", so...
            # The only way to be fine is to have a single element, like [1,2,2,2,3,3,3,...]
            #     - If we have more of the smallest length, we're into trouble
            return True
        # Remove from \"b\"
        return True if ( D[b]==1 and (a+1)==b ) else False
    def maxEqualFreq(self, A):
        best = 0
        B = Counter() # Count number of repetitions/length (per value)
        C = Counter() # Count number of times a length has been seen
        for i,x in enumerate(A):
            if B[x]:
                # If we had seen B before, deregister its \"old\" length
                if C[B[x]] == 1:
                    C.pop( B[x] )
                else:
                    C[B[x]] -= 1
            B[x]    += 1 # increase rep. counter
            C[B[x]] += 1 # Register new length seen
            #
            if len(C)<=2 and self.isvalid(C):
                best = i+1
        return best

from collections import Counter 
    

class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        n = len(nums)
        res = n
        if n <= 2:
            return n
        
        c = set(cnt.values())
        min_c = min(cnt.values())
        max_c = max(cnt.values())
        if (len(c) == 2 and ((sum([1 for k in cnt if cnt[k] == max_c]) == 1 and max_c == min_c + 1) or (sum([1 for k in cnt if cnt[k] == min_c]) == 1 and min_c == 1))) or (len(c) == 1 and min_c == 1) or (len(cnt) == 1):
            return res
        # print(cnt, min_c, max_c)
        
        for i in reversed(nums[2:]):
            res -= 1
            cnt[i] -= 1
            if cnt[i] == 0:
                del cnt[i]
            
            if not cnt:
                return res
            c = set(cnt.values())
            min_c = min(cnt.values())
            max_c = max(cnt.values())
            if (len(c) == 2 and ((sum([1 for k in cnt if cnt[k] == max_c]) == 1 and max_c == min_c + 1) or (sum([1 for k in cnt if cnt[k] == min_c]) == 1 and min_c == 1))) or (len(c) == 1 and min_c == 1) or (len(cnt) == 1):
                return res
        
        return 2


class Solution:
    # hashmap
    # review
    def maxEqualFreq(self, nums: List[int]) -> int:
        count = collections.defaultdict(int)
        freq = collections.defaultdict(int)

        # for test case [1,1,1,2,2,2] , the ans is 5, [1,1,1,2,2], len=5, you can remove 1, then 1 and 2 occur 2 times
        # we will get count {1:3, 2:3}
        # for freq: we would get {1:2, 2:2, 3: 2}, notice we loop from left to right, so we would get
        # freq : {1:1}, {1:1, 2:1}, {1:1,2:1,3:1}, {1:2,2:1,3:1}, {1:2,2:2,3:1},{1:2,2:2,3:2}
        for n in nums:
            count[n] += 1
            freq[count[n]] += 1

        for i in range(len(nums) - 1, 0, -1):
            # 2 case, case 1 , keep i, then you have to remove another on from 0 -- i-1
            # for test case [1,1,1,2,2,2], at index i = 5, 3 * 2 = 6 != 5, because we need to remove one element if we
            # want to keep ith element
            # but i = 4,  count[2] = 2, freq[2] = 2, 2 * 2 = 4, ie, when i = 4, total 5 elements, remove 1 ele, remain 4.
            # notice we need to return ri+1, because w need to prefix length, which include the removed element

            # this means from 0->i , each num appear equal times, then we just need to remove i+1
            if count[nums[i]] * freq[count[nums[i]]] == i:
                return i + 1
            freq[count[nums[i]]] -= 1
            count[nums[i]] -= 1

            if count[nums[i - 1]] * freq[count[nums[i - 1]]] == i:
                return i + 1

        return 1