LeetCode Entry
3005. Count Elements With Maximum Frequency
Count max-freq elements
3005. Count Elements With Maximum Frequency easy blog post substack youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/1120
Problem TLDR
Count max-freq elements #easy #counting
Intuition
Maintain frequency map. Count on-line or in the second iteration.
Approach
- for n=100 brute force is accepted
Complexity
-
Time complexity: \(O(n^2)\)
-
Space complexity: \(O(n)\)
Code
// 13ms
fun maxFrequencyElements(n: IntArray) =
n.groupBy{it}.values.map{it.size}.run {max()*count{it==max()}}
// 1ms
fun maxFrequencyElements(n: IntArray): Int {
var res = 0; var maxF = 0; val f = IntArray(101)
for (x in n) if (++f[x] > maxF) { maxF = f[x]; res = 1 }
else if (f[x] == maxF) ++res;
return res * maxF
}
// 0ms
pub fn max_frequency_elements(mut n: Vec<i32>) -> i32 {
n.sort_unstable(); n.chunk_by(|a, b| a == b)
.fold((0, 0, 0), |r, c| if c.len() > r.0 { (c.len(), 1, c.len())}
else if c.len() == r.0 { (r.0, r.1 + 1, r.0 * (r.1+1))} else { r }).2 as _
}