The majority element
A majority element is a value that appears in strictly more than half of the positions in a list. The Boyer Moore majority vote algorithm finds such an element in a single pass using only a couple of variables, with no extra storage for counts.
How the voting works
Keep two variables: a candidate and a count starting at zero.
- For each value, if the count is zero, adopt the current value as the candidate and set count to one.
- Otherwise, if the value equals the candidate, increase the count.
- If the value differs, decrease the count.
Think of it as pairing off opposing votes. Every non candidate cancels one candidate vote. Because the true majority appears more than half the time, it can never be fully cancelled, so it survives as the final candidate.
A needed second pass
The algorithm guarantees the right answer only when a majority truly exists. If you are not sure one does, do a quick second pass to count the candidate and confirm it really exceeds half.
Key idea
Cancel each non candidate against the candidate so the true majority is never eliminated, then verify with a second pass when existence is uncertain.