3004. Count Elements With Maximum Frequency

Problem Statement in English

You’re given a 0-indexed integer array nums. The frequency of an element is the number of times it appears in the array.

Return the sum of frequencies of elements that have the maximum frequency.

Approach

We just need a hashmap to solve this. To support an early exit, we can sort the frequency values in descending order and then iterate through them, summing up the frequencies until we encounter a frequency that is less than the maximum frequency.

Solution in Python

class Solution:
    def maxFrequencyElements(self, nums: List[int]) -> int:
        c = Counter(nums)
        l = sorted(c.values(), reverse=True)

        target = l[0]
        res = 0

        for x in l:
            if x == target:
                res += target
            else:
                break

        return res

Complexity

• Time: $O(n \log n)$, where $n$ is the length of the input list nums. This is due to the sorting step.

• Space: $O(n)$, where $n$ is the number of unique elements in nums. This is due to the space used by the counter and the sorted list.

And we are done.