Overview
The Boyer–Moore Majority Vote algorithm finds the value occupying more than half of an array using one counter and one candidate variable — no hash map, no sorting, no second array.
The idea is cancellation. Imagine pairing off each occurrence of the majority value with one occurrence of something else and deleting both. Since the majority strictly exceeds half, it cannot be fully cancelled — whatever survives to the end must be it. The counter is that pairing, done in a single pass without ever storing the pairs.
How Boyer–Moore Majority Vote works
- Start with no candidate and a counter of 0.
- For each element: if the counter is 0, adopt this element as the new candidate and set the counter to 1.
- Otherwise, if the element equals the candidate, increment the counter.
- If it differs, decrement the counter — this is one cancellation between the candidate and a non-candidate.
- After the pass, the candidate is the only possible majority. Run a second pass counting its occurrences to confirm it really exceeds n/2.
When to use it
- Consensus and fault tolerance: finding the value a majority of replicas or sensors agree on, in constant memory.
- Stream processing where the data is too large to store — the algorithm never keeps more than one value.
- Embedded and hardware voting circuits, where a hash map is not an option at all.
- Extended to find all elements appearing more than n/k times, by keeping k − 1 candidates and counters instead of one.
Complexity analysis
Time is O(n): one pass to find the candidate and one to verify it, both linear. Space is O(1) — two variables regardless of array size, which is what distinguishes it from the obvious hash-map solution at O(n) space. The verification pass is not optional: on an array with no majority the first pass still produces some candidate, and reporting it without checking is wrong.
Frequently asked questions
Why is the second pass mandatory?
Because the algorithm only guarantees 'if a majority exists, it is this candidate'. It says nothing when no majority exists — on [1, 2, 3] it will confidently hand back 3. Only counting can tell the two situations apart.
Does 'majority' mean most frequent?
No, and the difference matters. Majority means strictly more than n/2 occurrences. The most frequent value in [1, 1, 2, 2, 3] is 1 or 2 at two occurrences each, but neither is a majority, and this algorithm is not designed to find the mode.
Why can a wrong candidate never survive?
Every decrement pairs one majority element with one non-majority element. There are fewer than n/2 non-majority elements in total, so they run out before the majority does, and the counter cannot reach zero on the final stretch of majority values.