Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1224.html

1224. Maximum Equal Frequency

Level

Hard

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

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

Solution

For each prefix of nums, it is possible if one of the following cases is met.

  1. All elements in the prefix are different.
  2. All elements in the prefix are the same.
  3. Exactly one element occurs for n + 1 times and all the other elements occur for n times, where n is a positive integer.
  4. Exactly one element occurs once and all the other elements occur for n times, where n is a positive integer.

Use two maps to store each number’s frequency and for each frequency, how many numbers have such a frequency. Loop over nums from left to right and update the two maps. For each prefix, check whether it is possible using the cases. If it is possible, update the maximum length. Finally, return the maximum length.

  • class Solution {
    public int maxEqualFreq(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int maxLength = 1;
        Map<Integer, Integer> numFrequencyMap = new HashMap<Integer, Integer>();
        Map<Integer, Integer> frequencyCountMap = new HashMap<Integer, Integer>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            int frequency = numFrequencyMap.getOrDefault(num, 0);
            int newFrequency = frequency + 1;
            numFrequencyMap.put(num, newFrequency);
            if (frequency > 0) {
                int count = frequencyCountMap.get(frequency) - 1;
                if (count > 0)
                    frequencyCountMap.put(frequency, count);
                else
                    frequencyCountMap.remove(frequency);
            }
            int newCount = frequencyCountMap.getOrDefault(newFrequency, 0) + 1;
            frequencyCountMap.put(newFrequency, newCount);
            if (isPossible(frequencyCountMap))
                maxLength = i + 1;
        }
        return maxLength;
    }

    public boolean isPossible(Map<Integer, Integer> frequencyCountMap) {
        if (frequencyCountMap.size() > 2)
            return false;
        List<Integer> list = new ArrayList<Integer>(frequencyCountMap.keySet());
        if (list.size() == 1) {
            int key = list.get(0);
            if (key == 1)
                return true;
            int count = frequencyCountMap.get(key);
            return count == 1;
        } else {
            int min = list.get(0), max = list.get(1);
            if (min > max) {
                int temp = min;
                min = max;
                max = temp;
            }
            if (max - min == 1 && frequencyCountMap.get(max) == 1)
                return true;
            else if (min == 1 && frequencyCountMap.get(min) == 1)
                return true;
            else
                return false;
        }
    }
}

  • // OJ: https://leetcode.com/problems/maximum-equal-frequency/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    int maxEqualFreq(vector<int>& A) {
        unordered_map<int, int> cnt;
        map<int, int> freq;
        int N = A.size(), ans = 0;
        for (int i = 0; i < N; ++i) {
            int c = ++cnt[A[i]];
            if (c - 1 > 0) {
                if (--freq[c - 1] == 0) freq.erase(c - 1);
            }
            ++freq[c];
            if (freq.size() == 2) {
                auto &[a, ca] = *freq.begin();
                auto &[b, cb] = *freq.rbegin();
                if ((b == a + 1 && cb == 1) || (a == 1 && ca == 1)) ans = i + 1;
            } else if (freq.size() == 1) {
                auto &[a, ca] = *freq.begin();
                if (a == 1 || ca == 1) ans = i + 1;
            }
        }
        return ans;
    }
};

  • 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



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

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

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

All Problems

All Solutions