[LeetCode] Maximum Equal Frequency

1224. Maximum Equal Frequency

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).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
unordered_map<int,int> counter;
bool verify(int n) {
int diff = 0;
for(auto it = begin(counter); it != end(counter) and diff < 2; it++) {
diff += (it->second != n);
}
if(n == 1) return diff <= 1;
return diff == 1;
}
public:
int maxEqualFreq(vector<int>& nums) {

for(auto n : nums) counter[n]++;
for(int i = nums.size() - 1; i >= 0; i--) {
int a = counter.size();
if(i % a == 0 and verify(i/a)) {
return i + 1;
} else if(i % (a-1) == 0 and verify(i/(a-1))) {
return i + 1;
} else if(--counter[nums[i]] == 0)
counter.erase(nums[i]);
}
return 0;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/03/23/PS/LeetCode/maximum-equal-frequency/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.