Boyer-Moore Majority Voting Algorithm

The algorithm works if we are looking for identifying the elements that has the majority with $count > n/2$ elements. Note here that it's strictly greater than

[!important]
This algorithm only works if the given input is correct (have 1 element with count > n/2)

For example if we have something like

majorityElement([1,1,1,2,3,4,5])

The algorithm wouldn't work, because 1 only has 3 elements whereas n = 7. So $3 \ngtr 7/2$. In this case the algorithm will return 5 which is wrong.

However if we have more 1 like

majorityElement([1,1,1,1,2,3,4,5])

The algorithm will return 1

Implementation

def majorityElement(nums: List[int]) -> int:
    count = 0
    candidate = None

    for num in nums:
        if count == 0:
            candidate = num

        count += 1 if num == candidate else -1

    return candidate

majorityElement([1,1,1,1,2,3,4,5]) # 1

Time complexity: $O(n)$
Space complexity: $O(1)$