Hashing: Majority Element II

You are given an integer array nums of size \(n\). Find all elements that appear more than \(\lfloor n/3 \rfloor\) times. You may return the result in any order.

Answer

We simply count frequencies using a hashmap and then collect the elements whose counts exceed \(\lfloor n/3 \rfloor\).

Python
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        num_freq = defaultdict(int)
        res = []

        for num in nums:
            num_freq[num] += 1

        for num, freq in num_freq.items():
            if freq > (len(nums) // 3):
                res.append(num)

        return res

Time complexity: \(O(n)\). Optimal.

Space complexity: \(O(n)\). Suboptimal but good enough for interviews I would say.

Back to collection