Majority Element (Boyer-Moore)

Problem

Find the majority element (appearing more than n // 2 times) using the Boyer-Moore voting algorithm.

Maintain a candidate and a counter: when the counter reaches zero adopt the current value as the candidate, a matching value increments the counter, and a different value decrements it. After the pass, verify the candidate really exceeds n // 2.

Return the majority value, or None when no value qualifies (including for an empty list).

Hint

Pairing off different values leaves the majority candidate standing; verify it afterwards.

Test cases

case 1

in: [[3,2,3]]

expected: 3

case 2

in: [[2,2,1,1,1,2,2]]

expected: 2

case 3

in: [[1,2,3]]

expected: null

case 4

in: [[5]]

expected: 5

case 5

in: [[]]

expected: null

Starter codePython

def majority_element(nums):
    # Your code here
    pass

5 test cases · run your code against them in the editor