Coding Interview Patterns Module 3 – Arrays and hashing
Majority vote in O(1) space
Find the value that fills more than half of a list with O(1) extra memory using the Boyer–Moore vote, check it, and extend it to more than a third.
What you will learn
- Find a majority value with the Boyer–Moore vote in O(n) time and O(1) extra memory
- Check the candidate with a second pass when a majority is not promised
- Prove why a value with more than half of the items survives the cancellations
- Extend the vote to values that fill more than a third of the items
- Choose between counting, sorting and voting for a given memory limit
Before you start
What you’ll learn · Before you start
What you will learn
- Find a majority value with the Boyer–Moore vote in O(n) time and O(1) extra memory
- Check the candidate with a second pass when a majority is not promised
- Prove why a value with more than half of the items survives the cancellations
- Extend the vote to values that fill more than a third of the items
- Choose between counting, sorting and voting for a given memory limit
Before you start
On this page
A majority element: A value that fills more than half of a list, such as 4 in [4, 7, 4, 4, 2, 4]. A list has at most one, and exactly half is not enough. fills more than half of a list, as member 4 fills four of the six ballots [4, 7, 4, 4, 2, 4], and the Boyer–Moore vote finds it in one pass with two variables: a candidate and a counter. The vote pairs off items with different values, and because a majority value outnumbers all the others together, some of its items are never paired and it ends as the candidate. A second pass counts the candidate, since a list without a majority still produces one. The whole method takes O(n) time and O(1) extra memory, where counting every value needs a map as large as the number of distinct values. The problem usually called majority element appears here as an original ballot-box version, with its limits, and the obvious counts turn out too slow or too large.
The problem: an outright winner from a ballot box
The problem
A club elects its captain. Each ballot holds the member number of one candidate, and the ballots are read from the box one at a time, in no particular order. A candidate wins outright with more than half of the ballots. Return the winner’s member number, or −1 if nobody has more than half. The counting machine may read the ballots twice but can store only a handful of numbers, however many ballots there are. Limits: 1 to 10⁷ ballots, member numbers from 1 to 10⁹.
[4, 7, 4, 4, 2, 4]gives4: four of six ballots.[3, 3, 5, 5]gives−1: two of four is exactly half, not more.[9]gives9.
A majority survives the pairing
Text description of the diagram
The box holds six ballots: four for member 4 and one each for members 7 and 2.
- The ballot for 7 is paired with one ballot for 4, and the ballot for 2 with another.
- Two ballots for 4 are left over, because 4 has more ballots than all the other members together.
However the ballots are paired, as long as each pair holds two different members, ballots of a member with more than half of them are left over.
The brute force: count every candidate
For each ballot, count how many ballots name the same member, and stop at a member with more than half. With no winner, every ballot is compared with every ballot. Counting all members at once with a hash map is fast, but it breaks the machine’s memory rule:
"""The outright winner of a ballot box, by brute force: count every candidate's ballots with a scan."""
import tracemalloc
from collections import Counter
def winner_brute(ballots):
"""Returns (winner or -1, comparisons): for each ballot, count how many ballots name the same member."""
comparisons = 0
for candidate in ballots:
votes = 0
for ballot in ballots:
comparisons += 1
votes += ballot == candidate
if 2 * votes > len(ballots):
return candidate, comparisons
return -1, comparisons
print(winner_brute([4, 7, 4, 4, 2, 4])[0])
print(winner_brute([3, 3, 5, 5])[0])
print(winner_brute([9])[0])
# The slowest case is a box with no winner: every ballot's candidate is counted against every ballot.
for n in (1_000, 2_000):
print(f"n = {n:,}: {winner_brute(list(range(n)))[1]:,} comparisons")
# Counting every candidate at once is fast, but it needs memory for every member number that appears.
ballots = list(range(1, 200_001)) # 200,000 different members, one ballot each
tracemalloc.start()
counts = Counter(ballots)
peak = tracemalloc.get_traced_memory()[1]
tracemalloc.stop()
print(f"a Counter of {len(counts):,} members: at most {peak // 1024:,} KiB allocated")Output
4 -1 9 n = 1,000: 1,000,000 comparisons n = 2,000: 4,000,000 comparisons a Counter of 200,000 members: at most 15,362 KiB allocated
This output changes from run to run: the memory a Counter takes depends on the size of Python's integers and references, 64-bit or 32-bit
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 count_each.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
The scans make n² comparisons: 10¹⁴ for 10⁷ ballots. The map stores every distinct member; at 200,000 members it already took about 15 MiB in the recorded run, and 10⁷ distinct members would take about fifty times that. Step through the second example, where every scan runs to the end:
The drawing shows the whole scene; its 6 steps are listed below.
Every step as text
- Four ballots. The box holds 3, 3, 5 and 5. The brute force takes each ballot's member in turn and counts it with a scan of the whole box.
- Ballot 0 names 3. The scan compares all four ballots with 3 and finds two. 2 of 4 is not more than half. 4 comparisons so far.
- Ballot 1 names 3. The same member is counted again, with another full scan: 2 of 4 once more. 8 comparisons so far.
- Ballot 2 names 5. Two ballots name 5: 2 of 4. 12 comparisons so far.
- Ballot 3 names 5. A last full scan finds 5 twice again. After 16 comparisons nobody has more than half, so the answer is −1.
- Why it is slow. With no winner, every ballot is compared with every ballot: n² comparisons, 16 here and 10¹⁴ for 10⁷ ballots.
What to notice
A majority member has more ballots than all the other members together. Pair each ballot for any other member with one ballot for the majority member: the other ballots run out first, so some ballots for the majority member are always left over, as the figure shows. Three approaches are in common use:
- Counting with a hash map gives every member’s total in one pass, but needs memory for every distinct member.
- Sorting the ballots puts a majority member at the middle position, n // 2, in O(n log n) time.
- The Boyer–Moore vote keeps one candidate and one counter and cancels pairs of different ballots. A second pass counts the survivor, so two passes and O(1) extra memory settle the question.
Checkpoint
Check: An outright winner has more than half · Counting every candidate, and its cost · A majority outnumbers all the others
The practice below starts with whatever you know least.
Practice that adapts to you
Practise this lesson
9 questions about 9 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
The vote, step by step Pro: opens with a Pro, Premium or Ultimate pass
In this part:
- Why a majority survives: the invariant and the proof
- The vote and its check in 14 languages
- Counting against voting, measured
- More than a third: two candidates, two counters
- Variants, edge cases and the common bugs
- Variants
- Edge cases and common bugs
- Practice: every member with more than a third
- Every member with more than a third of the votes
- Interview questions
- A poll's votes are stored on 8 machines, about 10⁸ on each. Find the member with more than half of all the votes, if there is one, moving as little data as possible between machines. What does each machine compute, what does it send, and how do you confirm the answer?
- A stream of 10⁹ votes can be read only once, and you may keep only a few numbers. At the end you must report the majority member if there is one. What can you guarantee, and what is impossible?
- Find every URL that appears on more than 1 % of 10⁹ log lines, with 1 MB of memory and two passes over the log. How many candidates do you keep, what does each pass do, and what can you report if only one pass is allowed?
- Key takeaways
3 diagrams · 4 runnable examples (Python) · 1 exercise with sample tests · 3 interview answers · about 39 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Terms in this lesson
- heavy hitter
- A value whose count passes a fixed share of all the items of a stream, such as more than 1 % of them. Finding heavy hitters with little memory is a classic problem of stream processing.
- majority element
- A value that fills more than half of a list, such as 4 in [4, 7, 4, 4, 2, 4]. A list has at most one, and exactly half is not enough.
References
- MJRTY: A Fast Majority Vote Algorithm (R. S. Boyer and J S. Moore), in Automated Reasoning: Essays in Honor of Woody Bledsoe (Springer)
- Finding repeated elements (J. Misra and D. Gries), Science of Computer Programming 2(2) (Elsevier)
- collections.Counter (Python Software Foundation)
- tracemalloc: trace memory allocations (Python Software Foundation)
- Built-in types: common sequence operations (s.count(x)) (Python Software Foundation)
- The Java Language Specification, Java SE 25: 15.17.2 Division operator / (Oracle)
- The Go Programming Language Specification: arithmetic operators (The Go Authors)
- SE-0220: count(where:) (Swift.org (Swift Evolution))
- Java SE 25 API: Arrays (toString) (Oracle)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress