LC 169

Solution to LeetCode 169 Majority Element.

LeetCode 169

Majority Element (Easy). [link]

1] HashTable. Use HashTable to count the numbers. Return the number with most count.

Time complexity O(n), space complexity O(n), where n is the length of ‘nums’.

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        hash = {}
        for num in nums:
            if num not in hash:
                hash[num] = 1
            else:
                hash[num] += 1
        return max(hash, key = hash.get)

Use python API ‘Counter’.

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cnt = collections.Counter(nums)
        return max(cnt, key = cnt.get)

2] Sorting. Sort the array and return the number with index of floor(n/2).

Time complexity O(n log n), space complexity O(log n).

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        return nums[len(nums) // 2]

3] Divide and Conquer. If we split ‘nums’ into two parts, the mode of ‘nums’ must be the mode of at least one of the two parts. Using divide and conquer, we split the array into two parts, find the modes of the left part and the right part, then determine the correct mode of the two parts.

Time complexity O(n log n), space complexity O(log n).

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def recur(l, r):
            if l == r: return nums[l]
            
            m = l + (r - l) // 2
            left = recur(l, m)
            right = recur(m + 1, r)
            
            if left == right: return left # if two halves agree with the mode
            
            l_count = sum(1 for i in range(l, r + 1) if nums[i] == left)
            r_count = sum(1 for i in range(l, r + 1) if nums[i] == right)
            
            return left if l_count > r_count else right
        
        return recur(0, len(nums) - 1)

4] Boyer-Moore

Time complexity O(n), space complexity O(1).

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = 0
        candidate = None
        for n in nums:
            if count == 0:
                candidate = n # update canadidate for the mode
            count += (1 if n == candidate else -1) # final count must be non-negative
            
        return candidate