Problem. Given n values, return the majority element: the value that appears more than ⌊n/2⌋ times. Assume one exists.
[3, 2, 3] → 3
[2, 2, 1, 1, 1, 2, 2] → 2
ML context. Majority voting is everywhere in ML: combining labels from several annotators, aggregating predictions from an ensemble, picking the dominant class in a cluster, or finding the most common token in a huge stream with almost no memory.
This problem is a classic because its best solution, Boyer–Moore voting, uses O(1) memory, which feels impossible until you see the argument. We'll get there from a brute force, one constraint at a time.
1. Step 1: Clarify
| Question | Answer | Why it matters |
|---|---|---|
| Is a majority guaranteed? | Yes (for now) | Without it, the fast method needs a check pass |
| What values? | Any integers (or labels) | Rules out counting arrays for large ranges |
| n? | Up to 5 × 10⁴, maybe 10⁹ in a stream | Decides time and memory |
| Can I modify the input? | Maybe | Sorting in place needs it |
2. Step 2: Brute force: count each value
For each element, count how often it appears; return the one whose count exceeds n/2.
def majority_brute(nums):
n = len(nums)
for x in nums:
if sum(1 for y in nums if y == x) > n // 2: # O(n) count for each element
return x
return None
assert majority_brute([3, 2, 3]) == 3
assert majority_brute([2, 2, 1, 1, 1, 2, 2]) == 2
print("brute force works: O(n²) time, O(1) space")
O(n²) time, O(1) space. At n = 5 × 10⁴: about 2.5 × 10⁹ comparisons. Too slow, so optimise.
3. Step 3: Optimise, three ways
The repeated work: counting the same value again and again. Each optimisation removes it differently.
Optimisation A: count once with a hash map
from collections import Counter
def majority_hash(nums):
counts = Counter(nums) # O(n) time, O(distinct) space
value, freq = counts.most_common(1)[0]
return value if freq > len(nums) // 2 else None
assert majority_hash([2, 2, 1, 1, 1, 2, 2]) == 2
print("hash version: O(n) time, O(n) space")
O(n) time, but O(distinct values) memory: up to O(n).
Optimisation B: sort and take the middle
If a value fills more than half the positions, then in sorted order it must cover the middle position: no run longer than n/2 can avoid index n // 2.
def majority_sort(nums):
nums.sort() # O(n log n), in place
return nums[len(nums) // 2]
assert majority_sort([2, 2, 1, 1, 1, 2, 2]) == 2
assert majority_sort([3, 2, 3]) == 3
print("sort version: O(n log n) time, O(1) extra")
O(n log n) time, O(1) extra, but it modifies the input, and it's slower than hashing.
So far we trade time against memory. Can we have O(n) time and O(1) memory?
Optimisation C: Boyer–Moore voting
First principles: cancellation. Take any two different values and remove both. The majority loses at most one copy per removal, while the other values lose at least one too. Because the majority has more copies than all others combined, it can never be cancelled completely.
The algorithm performs those cancellations lazily, with just a candidate and a count:
- If the count is 0, take the current value as the new candidate.
- Same as the candidate → count + 1. Different → count − 1 (a cancellation).
import random
from collections import Counter
def majority_vote(nums):
candidate, count = None, 0
for x in nums:
if count == 0:
candidate = x # nothing left uncancelled: start over with x
count += 1 if x == candidate else -1
return candidate
assert majority_vote([2, 2, 1, 1, 1, 2, 2]) == 2
assert majority_vote([3, 2, 3]) == 3
rng = random.Random(14)
for _ in range(1000):
n = rng.randint(1, 30)
major = rng.randint(0, 5)
k = n // 2 + 1 + rng.randint(0, n - n // 2 - 1) # more than half are `major`
nums = [major] * k + [rng.randint(0, 5) for _ in range(n - k)]
rng.shuffle(nums)
assert Counter(nums)[major] > n // 2
assert majority_vote(nums) == major
print("Boyer–Moore: O(n) time, O(1) space, correct on 1,000 random cases")
- Time: O(n). Space: O(1): two variables, whatever n is.
- Why the final candidate is right: every decrement cancels one copy of the candidate against one different value. The majority can't be fully cancelled, so it's the candidate left standing.
Quick check
Why can Boyer–Moore voting find the majority with O(1) memory?
Show the answer
B. Each decrement cancels one copy of the candidate against a different value; a value with more than half the copies can't be cancelled entirely, so it survives as the candidate — Cancelling pairs of different values never removes all copies of a true majority, and a counter does that cancelling lazily.
4. When the constraints change
Change A: a majority is not guaranteed
Boyer–Moore always returns some candidate, even when no majority exists: on [1, 2, 3] it returns 3. So add a
second pass that counts the candidate. Still O(n) time and O(1) space.
def majority_or_none(nums):
candidate, count = None, 0
for x in nums:
if count == 0:
candidate = x
count += 1 if x == candidate else -1
return candidate if nums.count(candidate) > len(nums) // 2 else None # verify: O(n)
assert majority_or_none([1, 2, 3]) is None
assert majority_or_none([1, 1, 2]) == 1
assert majority_or_none([]) is None
print("with a verification pass: O(n) time, O(1) space")
Change B: find every value appearing more than n/3 times
At most two values can exceed n/3 (three would need more than n elements). Generalise the cancellation: keep two candidates; a value different from both cancels one copy of each. Then verify both.
import random
from collections import Counter
def more_than_third(nums):
c1, c2, n1, n2 = None, None, 0, 0
for x in nums:
if x == c1:
n1 += 1
elif x == c2:
n2 += 1
elif n1 == 0:
c1, n1 = x, 1
elif n2 == 0:
c2, n2 = x, 1
else:
n1 -= 1 # x cancels one copy of each candidate
n2 -= 1
return sorted({c for c in (c1, c2) if c is not None and nums.count(c) > len(nums) // 3})
rng = random.Random(15)
for _ in range(1000):
nums = [rng.randint(0, 4) for _ in range(rng.randint(0, 20))]
want = sorted(v for v, c in Counter(nums).items() if c > len(nums) // 3)
assert more_than_third(nums) == want
print("n/3 version: two candidates, O(n) time, O(1) space")
The pattern generalises: for "more than n/k", keep k − 1 candidates (the Misra–Gries summary), O(n·k) time and O(k) space.
Change C: the values arrive as an endless stream
Boyer–Moore needs one pass and O(1) memory: it works on a stream as-is. Verification needs a second pass, which a stream doesn't allow. Options: accept the candidate with a stated caveat, keep a sample, or use a frequency sketch (Misra–Gries, Count–Min) to estimate counts.
The full table
| If the constraint becomes… | Best approach | Time | Space |
|---|---|---|---|
| Memory is fine | Hash map counts | O(n) | O(distinct) |
| May sort in place | Sort, take middle | O(n log n) | O(1) |
| O(1) memory, majority guaranteed | Boyer–Moore | O(n) | O(1) |
| No guarantee | Boyer–Moore + verify | O(n), two passes | O(1) |
| More than n/3 | Two candidates + verify | O(n) | O(1) |
| More than n/k | k − 1 candidates (Misra–Gries) + verify | O(n·k) | O(k) |
| Values in a small range V | Counting array | O(n + V) | O(V) |
| Endless stream | Boyer–Moore or a frequency sketch | O(1) per value | O(1)–O(k) |
Quick check
On [1, 2, 3] Boyer–Moore returns 3. What does that show, and what's the fix?
Show the answer
A. It always returns a candidate, which is the majority only if one exists; without a guarantee, add a second pass that counts the candidate (still O(n) time, O(1) space) — The algorithm finds the only possible majority; verification confirms it actually is one.
5. Saying it out loud
"Brute force counts every value: O(n²). A Counter makes it O(n) time but O(n) memory; sorting puts the majority in the middle, O(n log n) with O(1) extra. For O(n) time and O(1) memory, I'll use voting: different values cancel in pairs, and a value with more than half the copies can't be cancelled out, so it's the surviving candidate. If a majority isn't guaranteed I'd verify with a second pass; for more than n/3 I'd keep two candidates."
Check yourself
- Why must the majority element occupy the middle position after sorting?
- State the cancellation argument behind Boyer–Moore.
- Why does Boyer–Moore need a verification pass when no majority is guaranteed?
- Why are at most two values more than n/3, and how many candidates for more than n/k?
- Which approach would you use for a stream of a billion labels, and what can't you do?
- When would a counting array beat all of these?
Answers
- A run of more than n/2 equal values in a sorted list must cover index n // 2.
- Removing pairs of different values never removes all copies of a value that makes up more than half; the counter performs those removals lazily, so the majority survives as the candidate.
- It always outputs some candidate; only a count confirms it's a real majority.
- Three values each above n/3 would need more than n elements; for more than n/k, keep k − 1 candidates.
- Boyer–Moore (one pass, O(1) memory), or a frequency sketch; you can't run a second verification pass.
- When values lie in a small range V: O(n + V) time, no comparisons.