VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 01: Arrays and strings

Lesson 1.6 of 16 in this moduleFree

Majority Element

Find the value that appears more than half the time: counting every value, hashing, sorting, and finally Boyer–Moore voting in O(n) time and O(1) space, with a proof by cancellation. Then the constraints change: no guarantee, more than n/3, and streams of labels.

about 10 min 6 Python examples 2 quick checks

Problem. Given n values, return the majority element: the value that appears more than ⌊n/2⌋ times. Assume one exists.

text
[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.

python
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

python
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.

python
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.

five copies of the majority value A paired against four other values; each pair is removed, and one A is always left over because A appears more than n/2 times.
Diagram— five copies of the majority value A paired against four other values; each pair is removed, and one A is always left over because A appears more than n/2 times.

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).
frames over [2, 2, 1, 1, 1, 2, 2]: the candidate starts as 2, the count falls to zero at index 3, 1 becomes the candidate, the count falls to zero again, and 2 becomes the final candidate.
Diagram— frames over [2, 2, 1, 1, 1, 2, 2]: the candidate starts as 2, the count falls to zero at index 3, 1 becomes the candidate, the count falls to zero again, and 2 becomes the final candidate.
python
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?

  1. It sorts the input first
  2. 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
  3. It uses a hidden hash map
  4. It guesses randomly and checks
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

a decision map: a hash map when memory is fine, sorting when the input may be sorted, Boyer–Moore with O(1) memory when a majority is guaranteed, Boyer–Moore plus a verification pass when it isn't, and two candidates for more than n/3.
Diagram— a decision map: a hash map when memory is fine, sorting when the input may be sorted, Boyer–Moore with O(1) memory when a majority is guaranteed, Boyer–Moore plus a verification pass when it isn't, and two candidates for more than n/3.

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.

python
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.

python
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?

  1. 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)
  2. The algorithm is broken
  3. 3 is the majority
  4. Sort first
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

  1. Why must the majority element occupy the middle position after sorting?
  2. State the cancellation argument behind Boyer–Moore.
  3. Why does Boyer–Moore need a verification pass when no majority is guaranteed?
  4. Why are at most two values more than n/3, and how many candidates for more than n/k?
  5. Which approach would you use for a stream of a billion labels, and what can't you do?
  6. When would a counting array beat all of these?
Answers
  1. A run of more than n/2 equal values in a sorted list must cover index n // 2.
  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.
  3. It always outputs some candidate; only a count confirms it's a real majority.
  4. Three values each above n/3 would need more than n elements; for more than n/k, keep k − 1 candidates.
  5. Boyer–Moore (one pass, O(1) memory), or a frequency sketch; you can't run a second verification pass.
  6. When values lie in a small range V: O(n + V) time, no comparisons.