'''
keys: 
Solutions:
Similar:
T:
S:
'''
from typing import List
import collections

class Solution:
    # Boyer-Moore Voting Algorithm
    # O(n) for T and O(1) for S
    def majorityElement2(self, nums):
        count = 0
        candidate = None

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

        return candidate
    
    # O(N) for S and T
    def majorityElement1(self, nums):
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)
    
        
    # O(nlogn) for T and O(1)/O(n) for S
    def majorityElement(self, nums):
        nums.sort()
        return nums[len(nums)//2]