class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:  
        freq_map = collections.defaultdict(int)
        for num in nums:
            freq_map[num] += 1
        
        res = []
        n = len(nums)
        for ele, cnt in freq_map.items():
            if cnt > n // 3:
                res.append(ele)
        return res

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

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:  
        count_map = collections.Counter(nums)
        n = len(nums)
        res = []
        for num, cnt in count_map.most_common(2):
            if cnt > n // 3:
                res.append(num)
        return res

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:  
        # 1st pass: Find candidates
        majority_map = defaultdict(int) # Track up to 2 candidates
        for num in nums:
            majority_map[num] += 1
            if len(majority_map) > 2:
                new_majority_map = defaultdict(int)
                for ele, cnt in majority_map.items():
                    if cnt > 1:
                        new_majority_map[ele] = cnt - 1
                majority_map = new_majority_map
        
        # 2nd pass: Verify candidates
        res = []
        n = len(nums)
        for num in majority_map:
            if nums.count(num) > n // 3:
                res.append(num)
        return res