3005. Count Elements With Maximum Frequency (Array, Hash Table, Counting)

링크 - https://leetcode.com/problems/count-elements-with-maximum-frequency/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

1) Hash table

class Solution:
    def maxFrequencyElements(self, nums: List[int]) -> int:
        max_frequency = 0
        hash_table = defaultdict(int)
        for num in nums:
            hash_table[num] += 1
            max_frequency = max(max_frequency, hash_table[num])

        ans = 0
        for k, v in hash_table.items():
            if v == max_frequency:
                ans += max_frequency

        return ans

Time Complexity: O(n)

Space Complexity: O(n)

2) One Pass Hash table

class Solution:
    def maxFrequencyElements(self, nums: List[int]) -> int:
        hash_table = defaultdict(int)
        max_frequency = total_frequency = 0

        for num in nums:
            hash_table[num] += 1
            f = hash_table[num]

            if f > max_frequency:
                max_frequency = f
                total_frequency = f
            elif f == max_frequency:
                total_frequency += f

        return total_frequency

Time Complexity: O(n)

Space Complexity: O(n)