169-MajorityElement

Majority Element

Problem can be found in here!

Basic Solution: Brute Force

def majorityElement(nums: List[int]) -> int:
    for i in range(len(nums)):
        counter = sum(1 for number in nums if number == nums[i])
        if counter > len(nums) // 2:
            return nums[i]

Time Complexity: , Space Complexity:

Improved Solution: Hash Table

def majorityElement(nums: List[int]) -> int:
    memo = {}
    threshold = len(nums) // 2
    for number in nums:
        try:
            memo[number] += 1
        except KeyError:
            memo[number] = 1

        if memo[number] > threshold:
                return number

Time Complexity: , Space Complexity: