What is the Boyer-Moore majority vote algorithm?

It finds the majority element — a value appearing more than n/2 times — in a single pass using only a candidate variable and a counter. Scanning left to right: if the counter is zero, adopt the current element as candidate with count 1; if the current element equals the candidate, increment; otherwise decrement. Whatever candidate remains at the end is the majority, if one exists.

Why does the cancellation trick work?

Think of each non-candidate element as cancelling one candidate vote. If a value truly appears more than half the time, it has more votes than all other values combined, so it can never be fully cancelled out — it survives. Every decrement pairs off one majority element with one non-majority element, and there simply aren't enough non-majority elements to eliminate the true majority.

Do you need a verification pass?

The algorithm guarantees the correct answer only if a majority element actually exists. If you are not sure one does, run a second O(n) pass to count how often the surviving candidate appears and confirm it exceeds n/2. That keeps the whole thing O(n) time and O(1) space.

How is this better than a hash map?

A hash map of counts also finds the majority in O(n) time but uses O(k) space for the distinct values. Boyer-Moore uses O(1) space — just two variables — which matters for huge or streaming inputs where you can't afford to store counts for every distinct element.

Algorithms · Majority Element

The Last One Standing.

One value appears more than half the time in this list. Find it — without a hash map, without sorting, in a single pass, using just two variables. The Boyer-Moore majority vote treats the scan like an election where every different vote cancels a candidate’s. If a value truly holds the majority, it can never be fully cancelled: it’s the last one standing.

O(n) time · O(1) space · one pass · streaming

majority

A value that occurs strictly more than n/2 times.

candidate

The current front-runner we’re tracking. One variable.

count

Net votes for the candidate. Hits zero → adopt the next element.

cancellation

A different value cancels one candidate vote. The core trick.

majority.js — two variables, one pass

Ready

A list where one value holds the majority. We track a single candidate and a count. Press Step: matches add a vote, mismatches cancel one, and when count hits 0 we adopt whoever’s next.

–

candidate

count

How it works

Imagine pairing off elements: every time you see a value different from your candidate, the two annihilate — one vote each, gone. A true majority element has more copies than everything else combined, so no matter how the pairings fall, some of it always survives to the end. That surviving value is the answer.

Count is zero → adopt

If count == 0, the current element becomes the new candidate with count = 1. The old candidate was fully cancelled.

Match → add a vote

If the element equals the candidate, count += 1. The lead grows.

Mismatch → cancel

Otherwise count -= 1 — this element cancels one of the candidate’s votes. Nobody new is adopted yet.

✓

Survivor is the majority

The candidate left standing at the end is the majority element (verify with a second pass if one isn’t guaranteed to exist).

Time

O(n)

Space

O(1)

Passes

1 (+1 to verify)

vs hash map

O(1) not O(k) space

The code

# majority element (> n/2), O(n) time, O(1) space def majority(a): cand, count = None, 0 for x in a: if count == 0: cand, count = x, 1 elif x == cand: count += 1 else: count -= 1 return cand # verify with a 2nd pass if unsure it exists

Two variables, no allocation — which is why it works on streams too, where you can’t store the whole input. The Boyer-Moore idea generalizes: to find all elements appearing more than n/3 times, keep two candidates and two counters.

Quick check

1. Why can a true majority element never be fully cancelled?

2. What’s the advantage over counting with a hash map?

FAQ

What is the majority element?

A value that appears strictly more than n/2 times in a list of n elements. At most one such value can exist.

What if no majority exists?

The algorithm still returns some candidate, but it may be wrong. If a majority isn’t guaranteed, add a second O(n) pass to count the candidate and confirm it exceeds n/2.

Does it work on a stream?

Yes — it only keeps two variables and looks at each element once, so it works even when you can’t store the whole input. That’s a defining property of streaming algorithms.

Can it find elements appearing more than n/3 times?

Yes, with the generalized Boyer-Moore: track two candidates and two counters. There can be at most two such values, and the same cancellation logic finds them.

Keep going

Finished this one? 0 / 62 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Real-time & Messaging Algorithms & DSA

The Last One Standing.

How it works

Count is zero → adopt

Match → add a vote

Mismatch → cancel

Survivor is the majority

The code

Quick check

FAQ

Keep going

Explore the topic

More Algorithms

Explore more from Vibe Engines

How it works

Count is zero → adopt

Match → add a vote

Mismatch → cancel

Survivor is the majority

The code

Quick check

FAQ

Keep going

Kadane’s Algorithm →

Hash Tables →

Top-K Frequent →

The DSA Roadmap →

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.