ARRAYS & HASHING · CORE

Boyer-Moore majority vote

Find the value that appears more than half the time using one pass and two variables, by letting different values cancel each other out.

Time O(n)Space O(1)3 practice problemsStep-through picture

The idea

A majority element is a value that appears more than half the time: in a list of 9 items, at least 5 times. Counting every value in a hash map finds it, but uses memory for every distinct value. The Boyer-Moore voting algorithm finds it with just two variables.

Keep a candidate and a count. Walk the list. When count is 0, the current value becomes the new candidate. Then a value equal to candidate adds 1 to count, and any other value subtracts 1. Think of each different value as cancelling out one copy of the candidate.

If a majority exists, it survives all the cancelling and is the candidate at the end. If there might be no majority, a second pass counts the candidate to check.

An everyday example

Last team standing

Picture a crowd where everyone wears a team shirt. People pair up with someone wearing a different shirt, and each such pair leaves the room. People wearing the same shirt can't pair up with each other. When no more pairs can form, everyone left wears the same shirt. If one team had more than half the people, they can't all be paired away, so they're the ones left.

How the example maps to the code
In the example	In the code
The shirt of the people currently left	`candidate`
How many of them are left	`count`
A pair of different shirts leaving	`count -= 1` for a value different from `candidate`
The room empties and a new group starts	`count === 0`, so `candidate = num`
Checking the team really had a majority	The second loop that counts `total`

From the slow way to boyer-moore majority vote

The obvious way to find a value that appears more than half the time: count every value in a hash map, then check the largest count. That is O(n) time but needs memory for every distinct value. Sorting and taking the middle item saves memory but costs O(n log n).
Here's a different view. Pair up two different values and throw both away. A majority value has more copies than all other values put together, so it can't run out of partners before the others do. Some copies of it must be left over.
That pairing can happen while reading the list once. Keep one candidate and a count of its unpaired copies. A copy of the candidate adds one; any other value pairs off with one copy and removes it.
When count drops to 0, everything read so far has been paired off, so the next value becomes the new candidate. If a majority isn't promised, a second pass counts the candidate to confirm it. That loop is the Boyer-Moore majority vote.

How it works

Start with candidate = null and count = 0.
For each num: if count is 0, make num the new candidate.
If num equals candidate, add 1 to count; otherwise subtract 1.
After the first pass, candidate is the only value that could be a majority.
Count how many times candidate really appears in a second pass.
Return candidate if it appears more than nums.length / 2 times, otherwise null.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…

See every step at onceThe same run, laid out side by side

Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor

function majority(nums) {
let candidate = null;
let count = 0;
for (const num of nums) {
if (count === 0) {
candidate = num;
}
count += num === candidate ? 1 : -1;
}
let total = 0;
for (const num of nums) {
if (num === candidate) total++;
}
return total > nums.length / 2 ? candidate : null;
}

How fast it is

Time	`O(n)`
Extra memory	`O(1)`

Two passes over the list, each doing constant work per item. Only candidate, count, and total are stored.

Best caseO(n)
Every input needs both passes in full, even [5, 5, 5]: 2n steps.
Average caseO(n)
Two passes with constant work per item, whatever the values.
Worst caseO(n)
No input is slower. If a majority is promised, you can skip the second pass, but it's still O(n).

Common mistakes

Skipping the second pass when a majority isn't guaranteed. The first pass returns a candidate even when there is no majority.
Thinking the final count is how many times the candidate appears. It is only what's left after cancelling.
Using total >= nums.length / 2. A majority needs strictly more than half.
Applying the single-candidate version to a "more than n / 3" problem, which needs two candidates.

When to use it

Look for these clues in a problem:

The problem asks for a value that appears more than n / 2 times (or more than n / 3, with two candidates).
You must use O(1) extra space.
The data is a long stream you can read once or twice but can't store.
The problem says a majority is guaranteed, or asks you to return a sign that none exists.

Check yourself

Answer each one in your head first, then open it.

In the trace, the first pass ends with count 1. How many 6s are there?

5. count only says how many copies were left after cancelling, not how many there are.

Why does [4, 4, 1, 2] return null?

4 appears 2 times out of 4, and the check is 2 > 2, which is false. Half is not a majority.

Can a list have two different majority values?

No. Each would need more than half of the items, and two such groups would add up to more than the whole list.

Why is the second pass needed when no majority is promised?

The first pass always ends with some candidate. In [1, 2, 3] it is 3, which appears once. Only counting can tell a real majority from a leftover.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

#69Votes Above a Third

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The first pass keeps one rule: the values read so far split into cancelled pairs, each made of two different values, plus count unpaired copies of candidate. Each step keeps it: a value matching the candidate joins the unpaired copies, a different value forms a pair with one of them, and when count is 0 the next value starts a new pile.

Suppose a majority value m exists but isn't the final candidate. Then no copy of m is left unpaired, so every copy sits in a cancelled pair. Each pair holds two different values, so at most one copy of m per pair, and each pair also holds one other value. That means there are at least as many other values as copies of m, so m can't be more than half. This contradiction shows the final candidate must be m.

The argument needs a majority to exist. Without one, the first pass still ends with some candidate, and nothing makes it special. That is why the second pass counts the candidate and returns it only if total > nums.length / 2.

Going deeper

3 more ideas

Why the majority survives

Each time count goes down, one copy of the candidate is cancelled by one different value. Every cancellation uses up one non-majority value for each majority value it removes. A majority has more copies than all other values put together, so the other values run out before the majority does, and the majority must be the candidate at the end.

Why the second pass is needed

The first pass always ends with some candidate, even when no majority exists. In [1, 2, 3], the candidate ends as 3, which appears only once. If the problem promises a majority, you can skip the check; otherwise count the candidate and compare with nums.length / 2.

More than a third

At most two values can each appear more than n / 3 times. Keep two candidates with two counts. A value matching either candidate adds to its count; a value that matches neither fills an empty slot or, if both are taken, subtracts 1 from both counts. Then verify both candidates with a second pass.

Work it by hand

Every step in a table, with why

Find the majority in 9 numbers where 6 appears 5 times. The candidate changes several times before settling.

nums = [6, 2, 2, 6, 6, 9, 6, 6, 2]

Step	`num`	`count` was 0?	`candidate`	`count` after	What happens	Why
1	6	yes	6	1	6 becomes the candidate	`count` starts at 0, so the first value is always picked.
2	2	no	6	0	2 cancels one 6	A different value pairs off with the only unpaired 6.
3	2	yes	2	1	2 becomes the candidate	Everything so far was paired off, so the candidate restarts with this `2`.
4	6	no	2	0	6 cancels the 2	The candidate `2` loses its only copy.
5	6	yes	6	1	6 is the candidate again	`count` was 0, so `6` takes over again.
6	9	no	6	0	9 cancels one 6	Any value that isn't the candidate cancels, even one seen only once.
7	6	yes	6	1	6 restarts as candidate	The first six values formed three cancelled pairs. This `6` is left unpaired.
8	6	no	6	2	Same value: count up	A second unpaired 6.
9	2	no	6	1	2 cancels one 6	The first pass ends with candidate `6` and `count` 1.
10	second pass	-	6	`total = 5`	`5 > 4.5`: return 6	Counting confirms that `6` appears 5 times, more than half of 9.

It returns 6. The final count is only 1, even though 6 appears 5 times, because count measures copies left after cancelling, not how often a value appears.

Compared with other ways

When to pick something else

Approach	Time	Extra memory	Choose it when
Boyer-Moore majority vote	`O(n)`	`O(1)`	You need the majority with constant extra memory, or in one pass over a stream.
Counting with a hash map	`O(n)`	`O(n)`	You also want other counts, or a looser rule like "the most common value".
Sort and take the middle	`O(n log n)`	`O(1)`	The list is sorted already. A majority must sit at index `Math.floor(n / 2)`, so check that item's count.

Extra memory: O(1): candidate, count, and total, however long the list is.

How the steps grow

Boyer-Moore majority vote, Counting with a hash map O(n)
Sort and take the middle O(n log n)

About how many steps for bigger inputs
Approach	n = 10	n = 1,000	n = 1,000,000
Boyer-Moore majority vote	10	1,000	1 million
Counting with a hash map	10	1,000	1 million
Sort and take the middle	33	9,966	20 million

Inputs that need care

5 tricky inputs

An empty list: nums = []: The first pass leaves candidate as null, total is 0, and 0 > 0 is false, so it returns null.
Exactly half: nums = [4, 4, 1, 2]: The candidate is 4 with total = 2, but 2 > 2 is false, so it returns null. A majority needs strictly more than half.
No majority: nums = [1, 2, 3]: The candidate ends as 3, the second pass counts 1, and it returns null.
The majority comes last: nums = [1, 2, 3, 3, 3]: 1 and 2 cancel each other, then 3 builds up. It returns 3.
The majority value is null: [null, null, 7]: It returns null, which looks exactly like "no majority". Return a separate flag if null can be a real value.

Variations and follow-ups

Twists interviewers add

More than `n / k` times

Keep k - 1 candidates with a count each. A value that matches none fills an empty slot, or else subtracts 1 from every count. At most k - 1 values can appear more than n / k times, and all of them survive. Verify each with a second pass.

A stream with a promised majority

If the problem guarantees a majority, the first pass alone is enough, so it can run over a stream that you read only once and can't store.

Divide and conquer

A majority of the whole list must be a majority of at least one half. Find each half's candidate and count both in the whole list. This takes O(n log n) and is a classic exercise in that style of proof.

In an interview

Spot it, explain it, answer follow-ups

Spot it from "appears more than half the time", "more than n / 3", or a request for O(1) extra space in a counting problem.
Explain it as cancelling pairs: "every different value cancels one copy of the candidate, and a majority can't be fully cancelled."
Test by hand: a list with no majority, a list with exactly half, and a list where the majority appears only at the end.
The usual follow-up is "more than n / 3 times". Answer: two candidates and two counts, then verify both, because up to two values can qualify.

Where frontend code uses it

The same idea in real UI code

Checking in a Web Worker whether one choice won more than half of a long stream of poll or A/B test votes, without keeping a count for every choice.
Detecting the dominant value in a large sample, such as the text direction most nodes use, with constant memory.

Boyer-Moore majority vote

The idea

An everyday example

Last team standing

From the slow way to boyer-moore majority vote

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

Go further

Why it works

Going deeper

Why the majority survives

Why the second pass is needed

More than a third

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

More than `n / k` times

A stream with a promised majority

Divide and conquer

In an interview

Where frontend code uses it

Tuto

Hi, I'm Tuto

Give feedback

The idea

An everyday example

Last team standing

From the slow way to boyer-moore majority vote

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

Go further

Why it works

Going deeper

Why the majority survives

Why the second pass is needed

More than a third

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

More than n / k times

A stream with a promised majority

Divide and conquer

In an interview

Where frontend code uses it

Related algorithms

More than `n / k` times