# Maximum Equal Frequency
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-equal-frequency)
Canonical: https://scaleengineer.com/dsa/problems/maximum-equal-frequency
**Data structures:** Array, Hash Table
**Companies:** [American Express](https://scaleengineer.com/companies/american-express)
---
## Problem
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 <= 105`
* `1 <= nums[i] <= 105`

# Approaches
## Brute-Force with Prefix Re-computation
This approach iterates through all possible prefix lengths, from 1 to N. For each prefix, it computes the frequency of each number from scratch. Then, it checks if this prefix can satisfy the condition by removing exactly one element. This is the most straightforward way to conceptualize the problem but is computationally expensive.
**Time:** O(N^2), where N is the length of the array. For each of the N prefixes, we iterate through its elements to build the frequency maps, which takes O(N) time. · **Space:** O(K), where K is the number of distinct elements in the prefix. In the worst case, K can be up to N, so the space complexity is O(N).
**Pros:** Simple to understand and implement.; Directly models the problem statement by checking each prefix.
**Cons:** Highly inefficient due to repeated computations.; Will result in a 'Time Limit Exceeded' error on platforms with large test cases.
### Explanation
In this method, we systematically check every prefix of the input array `nums`. For each prefix of length `L`, we determine if it's possible to remove one element to make the frequencies of all remaining numbers equal.

To do this, we first build a frequency map (`count`) for all numbers in the current prefix. Then, we build a second map (`freq`) that maps frequencies to the count of numbers having that frequency. For example, if the prefix is `[2, 2, 3, 3, 4]`, the `count` map is `{2:2, 3:2, 4:1}` and the `freq` map is `{2:2, 1:1}`.

With the `freq` map, we can check in constant time if the prefix is a valid candidate. A prefix is valid if its `freq` map conforms to one of a few patterns that allow for a fix by removing one element. These patterns are:
1.  All numbers have the same frequency `f`, and either `f=1` or there's only one distinct number.
2.  All numbers but one have frequency `f`, and that one number has frequency `1`.
3.  All numbers but one have frequency `f`, and that one number has frequency `f+1`.

We keep track of the maximum length `L` for which these conditions hold and return it as the final answer.

```java
class Solution {
    public int maxEqualFreq(int[] nums) {
        int maxLen = 0;
        for (int i = 0; i < nums.length; i++) {
            // Consider prefix nums[0...i]
            Map<Integer, Integer> count = new HashMap<>();
            for (int j = 0; j <= i; j++) {
                count.put(nums[j], count.getOrDefault(nums[j], 0) + 1);
            }

            Map<Integer, Integer> freq = new HashMap<>();
            for (int c : count.values()) {
                freq.put(c, freq.getOrDefault(c, 0) + 1);
            }

            if (isFixable(freq)) {
                maxLen = i + 1;
            }
        }
        return maxLen;
    }

    private boolean isFixable(Map<Integer, Integer> freq) {
        if (freq.size() == 0) return true;
        if (freq.size() == 1) {
            int f = freq.keySet().iterator().next();
            int k = freq.get(f);
            return f == 1 || k == 1;
        }
        if (freq.size() == 2) {
            Iterator<Integer> it = freq.keySet().iterator();
            int f1 = it.next();
            int k1 = freq.get(f1);
            int f2 = it.next();
            int k2 = freq.get(f2);

            if ((f1 == 1 && k1 == 1) || (f2 == 1 && k2 == 1)) {
                return true;
            }
            if ((f1 == f2 + 1 && k1 == 1) || (f2 == f1 + 1 && k2 == 1)) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Initialize `maxLen = 0`.
- Loop `L` from 1 to `nums.length`.
- For each `L`, consider the prefix `nums[0...L-1]`.
- Create a `count` map to store the frequency of each number in this prefix.
- From the `count` map, create a `freq` map to store the frequency of frequencies (how many numbers have a certain frequency).
- Check if the `freq` map satisfies one of the conditions for the prefix to be "fixable":
  - **Case 1:** The `freq` map has only one entry `(f, k)`. The prefix is fixable if `f == 1` (all numbers appear once) or `k == 1` (only one distinct number in the prefix).
  - **Case 2:** The `freq` map has two entries `(f1, k1)` and `(f2, k2)`. The prefix is fixable if:
    - One entry is `(1, 1)`. This corresponds to removing a number that appears only once.
    - The frequencies are consecutive (e.g., `f2 = f1 + 1`) and the higher frequency `f2` corresponds to only one number (`k2 = 1`). This corresponds to decrementing the frequency of one number.
- If the prefix is fixable, update `maxLen = L`.
- After checking all prefixes, return `maxLen`.

## Single Pass with Frequency Tracking
This optimal approach processes the array in a single pass. It maintains two hashmaps to track frequencies dynamically: one for the frequency of each number and another for the frequency of those frequencies. At each element, it updates the counts and checks if the current prefix meets the criteria. This avoids the O(N^2) complexity of re-calculating for each prefix.
**Time:** O(N), where N is the length of the array. We iterate through the array once, and each hashmap operation takes, on average, O(1) time. · **Space:** O(K), where K is the number of distinct elements in the array. In the worst case, K can be up to N, so the space complexity is O(N) for the hashmaps.
**Pros:** Highly efficient with linear time complexity.; Scales well for large inputs, passing all test cases.
**Cons:** The logic for the conditions can be complex to derive and implement correctly.; Requires careful state management of two separate frequency maps.
### Explanation
We can solve this problem efficiently by iterating through the array once and maintaining the frequency state of the current prefix. We use two hashmaps:
- `count`: Stores the frequency of each number seen so far (e.g., `count[x] = 3` means `x` has appeared 3 times).
- `freq`: Stores the frequency of frequencies (e.g., `freq[c] = k` means `k` numbers have a frequency of `c`).

As we iterate through `nums` from left to right, we extend the prefix by one element `num = nums[i]`. We update `count[num]`. This changes the frequency of `num` from, say, `c-1` to `c`. Consequently, we must update the `freq` map: decrement `freq[c-1]` and increment `freq[c]`.

After each update, we check if the current prefix of length `i+1` is a valid candidate. The conditions for a valid prefix, based on the state of the `freq` map, are:
1.  **All elements appear once:** `freq` is `{1: k}`. Removing one leaves `k-1` elements with frequency 1.
2.  **Only one distinct element:** `freq` is `{f: 1}`. Removing one instance leaves the element with frequency `f-1`.
3.  **One outlier with frequency 1:** `freq` is `{f: k, 1: 1}`. Removing the element with frequency 1 leaves `k` elements with frequency `f`.
4.  **One outlier with frequency f+1:** `freq` is `{f: k, f+1: 1}`. Removing one instance of the element with frequency `f+1` makes its frequency `f`, so all `k+1` elements now have frequency `f`.

If any of these conditions are met at step `i`, we update our answer `maxLen` to `i+1`. The final `maxLen` is the answer.

```java
class Solution {
    public int maxEqualFreq(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>(); // num -> frequency
        Map<Integer, Integer> freq = new HashMap<>();  // frequency -> count of numbers
        int maxLen = 0;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            
            // Update count and freq maps based on the new element
            int prevCount = count.getOrDefault(num, 0);
            if (prevCount > 0) {
                freq.put(prevCount, freq.get(prevCount) - 1);
                if (freq.get(prevCount) == 0) {
                    freq.remove(prevCount);
                }
            }
            
            int currentCount = prevCount + 1;
            count.put(num, currentCount);
            freq.put(currentCount, freq.getOrDefault(currentCount, 0) + 1);
            
            // Check if the current prefix is a valid candidate
            boolean isValid = false;
            if (freq.size() == 1) {
                int f = freq.keySet().iterator().next();
                int k = freq.get(f);
                // Case 1: All numbers have frequency 1 (e.g., [1,2,3,4])
                // Case 2: Only one distinct number (e.g., [5,5,5,5])
                if (f == 1 || k == 1) {
                    isValid = true;
                }
            } else if (freq.size() == 2) {
                Iterator<Integer> it = freq.keySet().iterator();
                int f1 = it.next();
                int k1 = freq.get(f1);
                int f2 = it.next();
                int k2 = freq.get(f2);
                
                // Case 3: Remove a number that appears only once
                // e.g., [2,2,3,3,4], freq map is {2:2, 1:1}
                if ((f1 == 1 && k1 == 1) || (f2 == 1 && k2 == 1)) {
                    isValid = true;
                }
                // Case 4: Decrement a number's frequency by 1
                // e.g., [2,2,3,3,3], freq map is {2:2, 3:1}
                if ((f1 == f2 + 1 && k1 == 1) || (f2 == f1 + 1 && k2 == 1)) {
                    isValid = true;
                }
            }

            if (isValid) {
                maxLen = i + 1;
            }
        }
        return maxLen;
    }
}
```
### Algorithm
- Initialize a `count` map (number -> frequency), a `freq` map (frequency -> count), and `maxLen = 0`.
- Iterate through `nums` from `i = 0` to `nums.length - 1`.
- For each element `num = nums[i]`:
  - Get its previous frequency `prevCount` from the `count` map.
  - Update the `freq` map by decrementing the count for `prevCount` (if `prevCount > 0`).
  - Update the `count` map for `num` to its new frequency, `currentCount = prevCount + 1`.
  - Update the `freq` map by incrementing the count for `currentCount`.
- After updating the maps, check if the current prefix `nums[0...i]` is fixable by analyzing the `freq` map using the same conditions as the brute-force approach.
- If the prefix is fixable, update `maxLen = i + 1`.
- Return `maxLen` after the loop finishes.

# Solutions
### Java

```java
class Solution {
private
  static int[] cnt = new int[100010];
private
  static int[] ccnt = new int[100010];
public
  int maxEqualFreq(int[] nums) {
    Arrays.fill(cnt, 0);
    Arrays.fill(ccnt, 0);
    int ans = 0;
    int mx = 0;
    for (int i = 1; i <= nums.length; ++i) {
      int v = nums[i - 1];
      if (cnt[v] > 0) {
        --ccnt[cnt[v]];
      }
      ++cnt[v];
      mx = Math.max(mx, cnt[v]);
      ++ccnt[cnt[v]];
      if (mx == 1) {
        ans = i;
      } else if (ccnt[mx] * mx + ccnt[mx - 1] * (mx - 1) == i &&
                 ccnt[mx] == 1) {
        ans = i;
      } else if (ccnt[mx] * mx + 1 == i && ccnt[1] == 1) {
        ans = i;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxEqualFreq(vector<int> &nums) {
    unordered_map<int, int> cnt;
    unordered_map<int, int> ccnt;
    int ans = 0, mx = 0;
    for (int i = 1; i <= nums.size(); ++i) {
      int v = nums[i - 1];
      if (cnt[v])
        --ccnt[cnt[v]];
      ++cnt[v];
      mx = max(mx, cnt[v]);
      ++ccnt[cnt[v]];
      if (mx == 1)
        ans = i;
      else if (ccnt[mx] * mx + ccnt[mx - 1] * (mx - 1) == i && ccnt[mx] == 1)
        ans = i;
      else if (ccnt[mx] * mx + 1 == i && ccnt[1] == 1)
        ans = i;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxEqualFreq(self, nums: List[int]) -> int: cnt = Counter() ccnt = Counter() ans = mx = 0 for i, v in enumerate(nums, 1): if v in cnt: 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

```