How Does the Boyer-Moore Voting Algorithm Work?
Understand how the Boyer-Moore voting algorithm finds a majority element in O(n) time and O(1) space, with proof and code.
Expected Interview Answer
The Boyer-Moore voting algorithm finds a majority element (one appearing more than n/2 times) in a single O(n)-time, O(1)-space pass by treating each element as a vote that either strengthens or cancels a running candidate, relying on the fact that a true majority element cannot be fully canceled out by all other elements combined.
The algorithm maintains a candidate and a count, both starting empty. For each element, if count is zero, that element becomes the new candidate; then count increments if the element matches the candidate and decrements otherwise. Because a majority element outnumbers every other element combined, every possible full cancellation of its votes still leaves at least one vote remaining, guaranteeing it survives as the final candidate. The algorithm only guarantees a correct result when a majority element is known to exist; otherwise a second verification pass — counting the final candidate’s actual occurrences — is required, since a non-majority array can still produce some arbitrary "surviving" candidate. The technique generalizes to the Boyer-Moore majority vote II problem, which finds all elements appearing more than n/3 times using two candidates and two counters simultaneously.
- O(n) time, single linear pass
- O(1) space — no hash map or sorting needed
- Correctness proof rests on a simple cancellation argument
- Generalizes to n/3-threshold and streaming variants
AI Mentor Explanation
Think of a locker-room debate over who the standout player of the season is: each teammate’s opinion either backs the current "leader" opinion (raising confidence) or contradicts it (lowering confidence), and once confidence drops to zero, the next opinion becomes the new leading claim. If one player truly earned more nominations than every other player’s nominations combined, that player’s claim can survive being pitted one-for-one against every other opinion and still come out ahead in the end. This works because you are not counting anyone fully — you are just letting opinions cancel in pairs, which is far cheaper than tallying every player’s vote count separately. Only after the debate ends do you double-check by actually counting the surviving name’s nominations, in case no true standout existed at all.
Step-by-Step Explanation
Step 1
Initialize candidate and count
Start with candidate = None and count = 0 before scanning the array.
Step 2
Assign candidate when count hits zero
Whenever count is 0, set the current element as the new candidate.
Step 3
Increment or decrement count
Add 1 to count if the current element equals candidate, otherwise subtract 1.
Step 4
Verify if majority is not guaranteed
Run a second pass counting candidate’s actual occurrences to confirm it exceeds n/2 when existence is not guaranteed.
What Interviewer Expects
- Walk through the candidate/count update logic precisely, including the count-zero reassignment rule
- Explain the cancellation-based correctness argument, not just recite the steps
- State O(n) time and O(1) space explicitly
- Know when and why a verification pass is required
Common Mistakes
- Incrementing count before checking whether count was zero, mis-ordering the candidate reassignment
- Treating the algorithm as always correct without verification when majority existence is not guaranteed
- Confusing this with simple frequency counting instead of understanding the cancellation mechanism
- Failing to generalize the idea when asked about the n/3-threshold (majority vote II) variant
Best Answer (HR Friendly)
“The Boyer-Moore voting algorithm keeps one running candidate and a counter as it scans the array once: matching elements increase confidence in the candidate, differing elements decrease it, and when confidence hits zero, the next element becomes the new candidate. Because a true majority element cannot be fully canceled out by everything else combined, it always survives to the end, which is what makes the whole thing work in constant extra memory.”
Code Example
def boyer_moore_majority(nums):
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
occurrences = sum(1 for num in nums if num == candidate)
if occurrences > len(nums) // 2:
return candidate
return None # no true majority element existsFollow-up Questions
- Why is a second, verification pass sometimes necessary for correctness?
- How would you adapt this algorithm to find elements appearing more than n/3 times (majority vote II)?
- Could you run this algorithm on a data stream you can only pass over once, and what would that imply?
- How would you prove formally that a majority element always survives the cancellation process?
MCQ Practice
1. In the Boyer-Moore voting algorithm, when is the current candidate reassigned?
The candidate is reassigned to the current element precisely when count has dropped to zero, meaning all prior votes have canceled out.
2. Why does the surviving candidate correctly identify a true majority element?
Since a majority element appears more than n/2 times, even in the worst-case pairing against every other element it cannot be reduced to zero votes.
3. What is required to confirm the final candidate is a genuine majority element when existence is not guaranteed?
A simple recount of how many times the surviving candidate actually appears confirms whether it truly exceeds n/2 occurrences.
Flash Cards
What two variables does Boyer-Moore voting track? — A single running candidate and an integer count.
When does the candidate get reassigned during the scan? — Whenever count reaches zero.
Why does a true majority element always survive the algorithm? — It outnumbers all other elements combined, so it can never be fully canceled to zero votes.
What must you do if majority existence is not guaranteed? — Run a verification pass counting the final candidate’s actual occurrences.