169. Majority Element

• categories: Code, Interview Question, leetcode, Easy
• source: https://leetcode.com/problems/majority-element/
• topics: Array

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        ans = None
        count = 0
        for num in nums:
            if not count:
                ans = num
            if ans == num:
                count += 1
            else:
                count -= 1
        return ans

Approach : Boyer-Moore Voting Algorithm

Intuition

If we had some way of counting instances of the majority element as +1 and instances of any other element as −1, summing them would make it obvious that the majority element is indeed the majority element.

Algorithm

Essentially, what Boyer-Moore does is look for a suffix suf of nums where suf[0] is the majority element in that suffix. To do this, we maintain a count, which is incremented whenever we see an instance of our current candidate for majority element and decremented whenever we see anything else. Whenever count equals 0, we effectively forget about everything in nums up to the current index and consider the current number as the candidate for majority element.