Problem URL: Majority element II

We will count the frequency of each element in the array and return the elements whose frequency is greater than n//3. We will use a hashmap to store the frequency of each element, and a set to store the elements whose frequency is greater than n//3.

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        count = collections.Counter(nums)
        res = set()
        for num in nums:
            if count[num] > len(nums)//3:
                res.add(num)
        return list(res)

Time complexity: O(n)
Space complexity: O(n)