Overview
The Boyer-Moore majority vote algorithm finds an element that appears more than n/2 times in O(n) time and O(1) space. It keeps one candidate and a counter: matching elements increase the counter, different elements decrease it, and when the counter hits zero the next element becomes the new candidate.
It works because of pairwise cancellation: every non-majority element can cancel at most one majority element, and the majority has more copies than everything else combined, so it survives. The generalized version finds all elements appearing more than n/k times with k - 1 candidates, followed by a verification pass, as your repo explains for n/3.
Supporters of different candidates pair off and knock each other out, one against one. If one candidate has more supporters than all others combined, some of their supporters are still standing when the brawl ends.
When to use it
- Find the element that appears more than n/2 (or n/k) times.
- O(1) extra space is required, so a frequency map is not allowed.
- Data arrives as a stream and you cannot store it.
- A second pass is possible to verify candidates when a majority is not guaranteed.
Problem patterns it solves
Recognize it when: an element appears more than half the time (often guaranteed).
- 169. Majority Element
- 1150. Check If a Number Is Majority Element in a Sorted Array
Recognize it when: all elements appearing more than n/3 times; use k - 1 candidates and verify.
- 229. Majority Element II
Recognize it when: an element that is dominant in both parts of a split.
- 2780. Minimum Index of a Valid Split
Recognize it when: majority within subarrays; combine Moore with a segment tree or random sampling.
- 1157. Online Majority Element In Subarray
Where it is used in real software
The Misra-Gries algorithm, a generalization of Moore's vote, finds frequent items (top IPs, trending hashtags) in network and log streams with fixed memory.
Systems with replicated sensors or computations pick the value reported by a majority of replicas.
Identifying the dominant error code or the most active server from a stream of events without storing all events.
Key terms
- Candidate
- The element currently believed to be the majority.
- Count
- Net votes for the candidate after cancellations.
- Cancellation
- A different element removes one vote from the candidate.
- Verification pass
- A second scan counting the candidate's real frequency.
How it works, step by step
- 1Start with count = 0
No candidate yet.
- 2When count is 0, adopt the current element
candidate = x, count = 1.
- 3Same element: vote for it
count++.
- 4Different element: cancel
count--.
- 5Verify if not guaranteed
Count occurrences of the candidate in a second pass and check > n/2.
STEP 1count = 0, adopt candidate = 2, count = 1.
Majority Element II (> n/3) with two candidates
nums = [1, 1, 1, 3, 3, 2, 2, 2], n = 8, threshold = floor(8/3) = 2
| x | c1 | count1 | c2 | count2 | Action |
|---|---|---|---|---|---|
| 1 | 1 | 1 | - | 0 | adopt c1 |
| 1 | 1 | 2 | - | 0 | vote c1 |
| 1 | 1 | 3 | - | 0 | vote c1 |
| 3 | 1 | 3 | 3 | 1 | adopt c2 |
| 3 | 1 | 3 | 3 | 2 | vote c2 |
| 2 | 1 | 2 | 3 | 1 | cancel both |
| 2 | 1 | 1 | 3 | 0 | cancel both |
| 2 | 1 | 1 | 2 | 1 | adopt c2 |
NOWx: 1 | c1: 1 | count1: 1 | c2: - | count2: 0 | Action: adopt c1
Candidates are 1 and 2. Verification: 1 appears 3 times (> 2, keep), 2 appears 3 times (> 2, keep). Answer [1, 2]. Verification is required because candidates are only possibilities.
Implementation
function majorityElement(nums) { let candidate = null, count = 0; for (const x of nums) { if (count === 0) candidate = x; count += x === candidate ? 1 : -1; } return candidate; // guaranteed to exist in LeetCode 169} function majorityElementII(nums) { let c1 = null, c2 = null, n1 = 0, n2 = 0; for (const x of nums) { if (x === c1) n1++; else if (x === c2) n2++; else if (n1 === 0) { c1 = x; n1 = 1; } else if (n2 === 0) { c2 = x; n2 = 1; } else { n1--; n2--; } } // Verification pass n1 = n2 = 0; for (const x of nums) { if (x === c1) n1++; else if (x === c2) n2++; } const result = []; const threshold = Math.floor(nums.length / 3); if (n1 > threshold) result.push(c1); if (n2 > threshold) result.push(c2); return result;}Complexity and performance
One pass (two with verification).
O(k) for the n/k generalization.
Simpler, also gives exact counts.
Trade-offs
A frequency map is easier and gives all counts but uses O(n) memory. Moore's vote only identifies candidates, using O(1).
After sorting, the majority is at index n/2, but that costs O(n log n) and modifies or copies the data.
Variants and related techniques
Keep up to k - 1 candidates; when a new element has no slot, decrement all counters.
For each of 32 bits, count how many numbers have it set; the majority's bits are those set in more than n/2 numbers.
Common mistakes
- Skipping verification when a majority is not guaranteed.
Fix: In [1, 2, 3], the algorithm returns a candidate even though no majority exists.
- Wrong branch order in the n/3 version.
Fix: Check equality with c1 and c2 before checking whether a counter is zero, or the same value can occupy both slots.
- Using >= instead of > for the threshold.
Fix: Majority means strictly more than n/2 (or n/3).
Interview questions
Why does Moore's algorithm work?
Each cancellation removes one majority element and one non-majority element at most. Since the majority has more than half of all elements, it cannot be fully cancelled and ends as the candidate.
How many elements can appear more than n/3 times?
At most two, because three such elements would account for more than n elements in total.
Practice problems
| Problem | Difficulty | What it trains |
|---|---|---|
| 169. Majority Element | Easy | Single candidate. |
| 229. Majority Element II | Medium | Two candidates and verification. |
| 2780. Minimum Index of a Valid Split | Medium | Dominant element with prefix counts. |
| 1157. Online Majority Element In Subarray | Hard | Range majority queries. |