1224. Maximum Equal Frequency

Description

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⁵
1 <= nums[i] <= 10⁵

Solutions

Solution 1: Array or Hash Table

Thinking

We need the longest prefix from which deleting one element equalizes remaining frequencies. \(n \le 10^5\), so we cannot recount every prefix.

Keep value frequencies \(cnt\), the frequency-of-frequencies \(ccnt\), and the maximum frequency \(mx\). A prefix works iff all frequencies are \(1\); or they are only \(mx\) and \(mx-1\) with a unique value at \(mx\); or all are \(mx\) except one singleton.

We update both maps left to right and test the three shapes in \(O(1)\) from \(ccnt\) and \(mx\), recording the largest valid index.

We use \(cnt\) to record the number of times each element \(v\) appears in \(nums\), and \(ccnt\) to record the number of times each count appears. The maximum number of times an element appears is represented by \(mx\).

While traversing \(nums\):

If the maximum count \(mx=1\), it means that each number in the current prefix appears \(1\) time. If we delete any one of them, the remaining numbers will all have the same count.
If all numbers appear \(mx\) and \(mx-1\) times, and only one number appears \(mx\) times, then we can delete one occurrence of the number that appears \(mx\) times. The remaining numbers will all have a count of \(mx-1\), which meets the condition.
If, except for one number, all other numbers appear \(mx\) times, then we can delete the number that appears once. The remaining numbers will all have a count of \(mx\), which meets the condition.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the \(nums\) array.

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

func maxEqualFreq(nums []int) int {
    cnt := map[int]int{}
    ccnt := map[int]int{}
    ans, mx := 0, 0
    for i, v := range nums {
        i++
        if cnt[v] > 0 {
            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
}

function maxEqualFreq(nums: number[]): number {
    const n = nums.length;
    const map = new Map();
    for (const num of nums) {
        map.set(num, (map.get(num) ?? 0) + 1);
    }

    for (let i = n - 1; i > 0; i--) {
        for (const k of map.keys()) {
            map.set(k, map.get(k) - 1);
            let num = 0;
            for (const v of map.values()) {
                if (v !== 0) {
                    num = v;
                    break;
                }
            }
            let isOk = true;
            let sum = 1;
            for (const v of map.values()) {
                if (v !== 0 && v !== num) {
                    isOk = false;
                    break;
                }
                sum += v;
            }
            if (isOk) {
                return sum;
            }
            map.set(k, map.get(k) + 1);
        }
        map.set(nums[i], map.get(nums[i]) - 1);
    }
    return 1;
}

1224. Maximum Equal Frequency

Description

Solutions

Solution 1: Array or Hash Table

Comments