Majority Element
Arrays: lesson 14 of 14
Cancel the votes in pairs and the majority survives.
Lesson 14 of 14 · 5 min
Majority Element
Step 1 of 10
Hold one candidate and one count. Every disagreement cancels a pair.
The Idea
If one value fills more than half the array, then pairing each of its copies against a copy of anything else still leaves copies over. Boyer-Moore does that cancelling in one pass: hold a candidate and a count, add one when the value matches, subtract one when it does not, and adopt a new candidate whenever the count hits zero. Only a true majority can survive every cancellation.
Real-World Example
Counting a show of hands with no paper. Set one raised hand for the leader against one hand for anyone else and drop both from the tally. Whoever still has hands left at the end had more than half of them.
The Code
def majority(nums):
candidate, count = None, 0
for x in nums:
if count == 0: # nobody is holding the floor
candidate = x
count += 1 if x == candidate else -1
return candidate
print(majority([2, 2, 1, 3, 2, 2, 2])) # 2Your turn
Put the steps in the right order.
- The count hits zero, so the next value becomes the candidate
- Read the next value and compare it with the candidate
- Subtract one from the count, because the value differs
- Return the surviving candidate once the array runs out
Mini quiz
1 / 3