Visualize

Pattern visualizer

Majority Element

Boyer-Moore voting keeps just two variables: a candidate and a vote count. Matching elements add a vote, differing elements cancel one. The trick is WHY cancellation is safe: every cancellation destroys votes in PAIRS — one for the candidate, one against — and an element holding more than half the votes can never be fully paired away. Whoever survives all the cancellation must be the majority. Animated on: Find the element that appears more than ⌊n/2⌋ times in [2, 2, 1, 1, 1, 2, 2] (n = 7, so more than 3 copies)..

Boyer-Moore voting — paired cancellation

time O(n)space O(1)step 1 / 11
2
[0]
2
[1]
1
[2]
1
[3]
1
[4]
2
[5]
2
[6]
line 2

n = 7, so the majority element must appear more than ⌊7/2⌋ = 3 times. Instead of counting every value with a hash map, Boyer-Moore tracks ONE candidate and its net vote count, starting at 0.

Pseudocode
1FUNCTION majorityElement(nums):
2  set candidate to none, count to 0
3  FOR each x in nums:
4    IF count equals 0:
5      candidate = x   (adopt a new candidate)
6    add +1 to count if x equals candidate, otherwise subtract 1
7  RETURN candidate

← / → step · space play · Home restart

Where to practice Arrays

Practice Arrays problemsAll Arrays problemsBack to roadmap