LC 0169 [E] Majority Element

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # O(n), O(n)
        num_to_freq = Counter(nums)
        
        for num, freq in num_to_freq.items():
            if freq > n/2:
                return num
        
    def majorityElement(self, nums):
        # O(n), O(1)
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate