LeetCode 169. Majority Element

Question: https://leetcode.com/problems/majority-element/

This is one of those popular questions that have multiple solutions. The easiest to come up with is simply iterate through the array and count the occurrences. The Efficiency of this solution is O(N). This takes 160 ms and 13.3 MB .

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """ 
        counts = {}
        n = len(nums)
        for num in nums:
            if num in counts:
                counts[num] += 1
                if counts[num] > n// 2:
                    break
            else:
                counts[num] = 1
        return num

Every time one encounters an array question, we should always think about whether sorting can help. In this case, once the array is sorted, we know that numbers of the same value are clustered, and we can increment the counter if the number under observation is the same as the previous value, and set the count back to 1 once a new value is encountered. This is O(NlogN) because of the sorting procedure. It takes 160ms and 14.2MB to run. This is rather strange, especially with the larger memory required compared to the count solution above.

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """ 
        n = len(nums)
        if n == 1:
            return nums[0]
        nums = sorted(nums)
        count = 1
        for i, num in enumerate(nums):
            if nums[i] == nums[i+1]:
                count +=1 
            else:
                count = 1
            if count > n//2:
                break
        return num

Now LeetCode's solution page has 6 different ways of solving this. I find the Boyer–Moore majority vote algorithm to be very clever and efficient. It takes only 144 ms and 13.3MB to run. By far the best solution. People can get confused about the definition of majority element. It is defined as any element that has a count greater than n//2, not the element with the largest count! For instance, let's say we have an array [7,7,5,5,1,1,7]. At first glance, it looks like 7 is the majority element. However, this is not true, there is no majority element in this array, because even 7 has only a count of 3, which is equal to 7//2=3, not exceeding n//2! So this array would not satisfy as a valid input to the question. The algorithm works exactly because of this property. The key property is this: when we encounter a tie (count=0) at index k, the majority element in [k:] will be the majority element of the original array. It takes some time to fully digest this. 

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """ 
        count = 0
        candidate = None

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

        return candidate