Majority Element

Boyer-Moore voting — paired cancellation

time O(n)space O(1)

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.

Details

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).

Problem:Majority ElementEasy

Boyer-Moore voting — paired cancellation

step 1 / 11

[0]

[1]

[2]

[3]

[4]

[5]

[6]

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.

i=0· arr[0] = 2

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

Every step in words

Show all 11 steps

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.
count is 0 — no candidate is defended right now, so the current element takes the seat: candidate = 2, then its own vote makes count = 1.
nums[1] = 2 matches the candidate, so it votes FOR it: count = 1 + 1 = 2. Two supporters, zero opposition so far.
nums[2] = 1 differs from candidate 2, so it cancels one supporter: count = 2 - 1 = 1. Note what just happened: one 2-vote and one 1-vote annihilated each other — a PAIR of different elements left the race together.
nums[3] = 1 cancels the last supporter: count = 1 - 1 = 0. The whole prefix [2, 2, 1, 1] has annihilated itself — two 2s paired off against two 1s.
WHY forgetting that prefix is safe: cancellation removed 2 copies of the majority and 2 copies of everything else — equal losses. 2 held 4 of 7 votes overall; after discarding the prefix it still holds 2 of the 3 remaining. A true majority can lose one vote per pair forever and still outnumber the rest.
count is 0 again, so the seat is open — nums[4] = 1 becomes the new candidate with count = 1. Yes, a MINORITY element can hold the seat temporarily; the pairing argument guarantees it cannot hold it to the end.
nums[5] = 2 differs from candidate 1 and cancels it: count = 1 - 1 = 0. Running tally of everything cancelled so far: three 2s versus three 1s — six elements gone, all in mixed pairs.
count is 0 once more, so the final element nums[6] = 2 takes the seat: candidate = 2, count = 1. The majority had 4 votes against 3 — after every possible pairing, exactly one unpaired 2 HAD to remain.
The scan is over and count = 1 > 0 — candidate 2 survived all cancellation. Since the problem guarantees a majority exists, the survivor must be it (without that guarantee you'd add a second pass to verify the count).
Answer: 2. Check it: 2 appears 4 times in 7 elements — more than ⌊7/2⌋ = 3. One pass, two variables: O(n) time, O(1) space, where a hash-map count would have needed O(n) extra space.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Majority Element in the editor All Arrays problems Back to roadmap