Solution Explanation for LeetCode 1224: Maximum Equal Frequency

This problem asks to find the longest prefix of an array such that removing exactly one element makes all remaining elements have the same frequency. The optimal solution leverages frequency counting to achieve linear time complexity.

Approach:

The core idea is to maintain two frequency counters:

1. cnt: Stores the frequency of each number in the current prefix. cnt[x] gives the count of number x.
2. ccnt: Stores the frequency of the frequencies themselves. ccnt[f] gives the count of how many numbers have a frequency of f.

We iterate through the nums array. For each element:

• Update cnt: Increment the count for the current number.

• Update ccnt: Decrement the count of the previous frequency of the number (if it existed) and increment the count of the new frequency.

• Check for conditions: We check three conditions to see if the current prefix satisfies the problem's criteria after removing one element. These conditions cover all possible scenarios where removing one element leads to equal frequencies:

  • Condition 1: mx == 1: If the maximum frequency (mx) is 1, removing any element results in all remaining elements having a frequency of 0.
  • Condition 2: ccnt[mx] * mx + ccnt[mx - 1] * (mx - 1) == i && ccnt[mx] == 1: This condition checks if all elements have a frequency of mx except one which has a frequency of mx-1. Removing the element with frequency mx makes all frequencies equal to mx-1.
  • Condition 3: ccnt[mx] * mx + 1 == i && ccnt[1] == 1: This condition checks if all elements have frequency mx except one element with frequency 1. Removing the element with frequency 1 results in all frequencies being mx.

Time Complexity: O(n), where n is the length of the input array. We iterate through the array once, and all other operations (hash map lookups and updates) take constant time on average.

Space Complexity: O(n) in the worst case, as the hash maps cnt and ccnt could store up to n distinct keys if all numbers in the input are unique.

Code Implementation (Python):

from collections import Counter
 
class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int:
        cnt = Counter()
        ccnt = Counter()
        ans = mx = 0
        for i, v in enumerate(nums, 1):  #enumerate starts from 1 for prefix length
            if cnt[v] > 0:
                ccnt[cnt[v]] -= 1
            cnt[v] += 1
            mx = max(mx, cnt[v])
            ccnt[cnt[v]] += 1
            if mx == 1:
                ans = i
            elif ccnt[mx] * mx + ccnt[mx - 1] * (mx - 1) == i and ccnt[mx] == 1:
                ans = i
            elif ccnt[mx] * mx + 1 == i and ccnt[1] == 1:
                ans = i
        return ans

Code Implementation (Java):

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public int maxEqualFreq(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        Map<Integer, Integer> ccnt = new HashMap<>();
        int ans = 0;
        int mx = 0;
        for (int i = 1; i <= nums.length; ++i) {
            int v = nums[i - 1];
            cnt.put(v, cnt.getOrDefault(v, 0) + 1);
            mx = Math.max(mx, cnt.get(v));
 
            ccnt.put(cnt.get(v)-1, ccnt.getOrDefault(cnt.get(v)-1,0) -1); //update ccnt before cnt update
            ccnt.put(cnt.get(v), ccnt.getOrDefault(cnt.get(v),0) + 1);
 
 
            if (mx == 1) {
                ans = i;
            } else if (checkCondition(ccnt, mx, i) || checkCondition2(ccnt,mx,i)) {
                ans = i;
            }
        }
        return ans;
    }
 
    private boolean checkCondition(Map<Integer, Integer> ccnt, int mx, int i){
        return ccnt.getOrDefault(mx, 0) * mx + ccnt.getOrDefault(mx - 1, 0) * (mx - 1) == i && ccnt.getOrDefault(mx, 0) == 1;
 
    }
    private boolean checkCondition2(Map<Integer, Integer> ccnt, int mx, int i){
        return ccnt.getOrDefault(mx, 0) * mx + 1 == i && ccnt.getOrDefault(1, 0) == 1;
    }
}

The other language implementations (C++, Go, TypeScript) follow a very similar structure to these examples, adapting the syntax and data structures accordingly. The core logic of maintaining two frequency counters and checking the three conditions remains the same across all languages.