Boyer–Moore Majority Vote

Concept Overview

The Boyer-Moore Majority Vote algorithm finds a majority element in a sequence if one exists. A majority element is defined as an element that occurs strictly more than n/2 times in a sequence of length n. The algorithm accomplishes this efficiently in two passes (or phases) with O(n) time and O(1) voting state. This teaching view additionally stores the entered sequence and an O(n) event trace; it does not claim constant total storage.

Algorithm Phases

The algorithm operates in two distinct phases:

1. Cancellation Phase

This phase identifies a single candidate that might be the majority element. It maintains acandidate and a counter. Iterating through the sequence:

If the counter is 0, the current element becomes the candidate, and the counter is set to 1. Note: A retained candidate is not cleared when the counter hits 0; it is only overwritten when the next element is processed.
If the current element equals the candidate, the counter is incremented.
If the current element differs from the candidate, the counter is decremented.

The intuition is that any non-majority element is "canceled out" by pairing it with a different element. Because a majority element appears more than half the time, it cannot be fully canceled out, guaranteeing it will be the final candidate if a majority exists. However, a final candidate does not guarantee a majority exists.

2. Verification Phase

This phase counts the actual occurrences of the candidate found in the first phase by doing a second pass over the sequence. If the count is strictly greater than n/2, the candidate is confirmed as the majority. Otherwise, there is no majority element.

Worked Example

Let's manually trace the algorithm for the sequence 4,4,1,4,2 to verify its behavior and outcomes on specific input sequences.

Phase 1: Cancellation

Index 0, value 4: counter is 0, so candidate becomes 4, counter = 1.
Index 1, value 4: matches candidate (4), counter increments to 2.
Index 2, value 1: differs from candidate (4), counter decrements to 1.
Index 3, value 4: matches candidate (4), counter increments to 2.
Index 4, value 2: differs from candidate (4), counter decrements to 1.

The final candidate is 4.

Phase 2: Verification

Count occurrences of 4 in [4,4,1,4,2].
The count is 3.
Since 3 > 5/2 (2.5), 4 is the confirmed majority element. Expected result: Majority = 4, Occurrences = 3.

Experiment

Use the Boyer–Moore Majority Vote module to explore this algorithm interactively.

Set the Sequence to 1,2,3.
Click Finish. Notice how a candidate remains at the end of the cancellation phase, but the verification phase shows it has only 1 occurrence (1 is not > 1.5). Thus, there is No majority.
Click Reset and change the Sequence to 2,1,2,2,3,2,2.
Use Step to advance one event at a time, observing how the counter increments on matches and decrements on mismatches, before transitioning to the verification phase to count occurrences.

Limitations

There are inherent limitations and conditions for using the Boyer-Moore Majority Vote algorithm effectively:

Strict Majority Required: The algorithm only finds an element if it appears strictly more than n/2 times. If the most frequent element appears exactly n/2 times or fewer, it will not be found as a majority. This limitation exists because without a strict majority, elements could completely cancel each other out in the worst case order.
Two Passes Needed: While O(n) time is efficient, the algorithm must read the data twice (unless it is guaranteed beforehand that a majority exists).

References

For further reading and the original presentation of the algorithm, refer to this detailed explanation:

Boyer, R. S., & Moore, J. S. (1991). MJRTY—A Fast Majority Vote Algorithm. In Automated Reasoning: Essays in Honor of Woody Bledsoe. Author's Example

Boyer–Moore Majority Vote