Moore's Voting Algorithm

Before we start

This is one of the most elegant algorithms in all of computer science — it looks like magic until you understand it, then it looks obvious. By the end of this page you will be able to:

• See the voting metaphor so clearly that the algorithm runs itself in your head.
• Explain out loud why the majority element can never be voted out.
• Apply it to both the n/2 and n/3 variants confidently.

Stop at every Pause & Think box. Those moments are where the real learning happens.

Picture this first (no code yet)

That town, those cancellations — that is Moore's Voting Algorithm. Let's make it precise.

The actual problem

Given an array of n integers, find the element that appears more than n/2 times (the majority element). You may assume it always exists.

Example:

input  = [3, 2, 3, 1, 3, 2, 3]
n = 7,  majority threshold = 7/2 = 3.5  →  need more than 3 appearances
3 appears 4 times  →  answer is 3

First, the slow way (so you feel the pain)

Approach 1 — count everything with a hash map:

from collections import Counter
def majorityElement(nums):
    count = Counter(nums)
    return max(count, key=count.get)

Correct, but uses O(n) extra memory for the hash map. For n = 100 million, that's potentially gigabytes of memory just to count. Can we do it with O(1) space?

Approach 2 — sort and pick the middle:

def majorityElement(nums):
    nums.sort()
    return nums[len(nums) // 2]   # middle element must be the majority

Also correct (a majority element must occupy the middle after sorting), but sorting costs O(n log n) time. Can we do it in O(n) time AND O(1) space?

n = 1,000,000
Sorting  →  ~20,000,000 operations
Voting   →  1,000,000 operations   (20x faster)

The turning point

Back to the town. The key insight is that we do not need to count everyone. We only need to track one candidate and a score that rises when we see someone supporting that candidate and falls when we see someone opposing.

When the score hits zero, all elements seen so far have perfectly cancelled each other out. They form a balanced group where no single value dominates. Whatever happened in that balanced group is completely irrelevant to what comes next — the majority element in the remaining unseen portion is still the majority element of the whole array (because all balanced cancellations removed equal numbers of majority and non-majority elements).

So when the score hits zero: reset the candidate to whatever comes next. Fresh start.

The one idea to remember

That's the whole algorithm. One pass, two variables.

Watch it happen, frame by frame

Array: [2, 2, 1, 1, 1, 2, 1]. The majority element is 1 (appears 4 times, n/2 = 3.5).

Start: candidate = None, score = 0

index 0 → value 2:  score == 0  →  candidate = 2, score = 1
index 1 → value 2:  value == candidate  →  score = 2
index 2 → value 1:  value != candidate  →  score = 1
index 3 → value 1:  value != candidate  →  score = 0
index 4 → value 1:  score == 0  →  candidate = 1, score = 1
index 5 → value 2:  value != candidate  →  score = 0
index 6 → value 1:  score == 0  →  candidate = 1, score = 1

Final candidate = 1  ✅

Notice what happened at index 3: 2 and 1 had perfectly cancelled each other out (two 2s vs two 1s). The slate wiped clean. Then 1 took over — and kept the throne.

index 0 → 3: score=0  →  candidate=3, score=1
index 1 → 3: match    →  score=2
index 2 → 4: differ   →  score=1
index 3 → 2: differ   →  score=0
index 4 → 3: score=0  →  candidate=3, score=1
index 5 → 3: match    →  score=2
index 6 → 3: match    →  score=3

Final candidate = 3  ✅  (appears 5 times, majority of 7)

Now, the code — line by line

def majorityElement(nums):
    candidate = None     # the current "town survivor" candidate
    score = 0            # net support count

    for num in nums:
        if score == 0:
            candidate = num    # slate wiped clean — this person is the new candidate
        if num == candidate:
            score += 1         # same party: gain support
        else:
            score -= 1         # different party: one cancellation

    return candidate

Mapping each line to the town story:

• candidate = None, score = 0 — the town hasn't started processing yet.
• if score == 0: candidate = num — the town is empty after all cancellations; whoever walks in next becomes the new hopeful.
• score += 1 — another supporter arrives; candidate's strength grows.
• score -= 1 — an opponent arrives; one supporter and one opponent cancel each other.
• return candidate — whoever survives the entire process is our answer.

Why does it never miss?

The argument is clean. Define the majority element as M (appears more than n/2 times).

Every time score decreases by 1, it means one occurrence of M cancelled with one non-M element. Since M appears more than n/2 times, there are not enough non-M elements to cancel all of them. At least one occurrence of M survives every possible round of cancellations.

The final candidate is whatever's left standing. Since M is the only element that cannot be fully cancelled, M is the final candidate.

Why is it so fast?

One for loop over the array. One comparison, one increment or decrement per element. No extra memory, no sorting.

n = 1,000,000   →   1,000,000 steps
n = 100,000,000 →   100,000,000 steps   (still under 1 second)

When should I reach for this? (the trigger list)

• The problem asks for an element that appears more than n/2 times or more than n/3 times.
• You need O(1) space — no hash maps allowed.
• The problem guarantees a majority exists (or asks you to verify after finding the candidate).
• Key phrase in problem: "majority element," "dominant element," "appears more than half the time."

The same trick in two disguises

Disguise 1 — Majority Element (LC #169)

Straightforward application. The problem guarantees a majority element exists.

def majorityElement(nums):
    candidate, score = None, 0
    for num in nums:
        if score == 0:
            candidate = num
        score += 1 if num == candidate else -1
    return candidate

Disguise 2 — Majority Element II: appear more than n/3 times (LC #229)

At most 2 elements can appear more than n/3 times (since 3 × (n/3+1) > n). So we track two candidates and two scores — the same cancellation logic, but now three-way: matching candidate1 → score1 up, matching candidate2 → score2 up, matching neither → both scores down by 1 (one triple cancellation).

def majorityElement2(nums):
    c1, c2, s1, s2 = None, None, 0, 0

    for num in nums:
        if num == c1:
            s1 += 1
        elif num == c2:
            s2 += 1
        elif s1 == 0:
            c1, s1 = num, 1
        elif s2 == 0:
            c2, s2 = num, 1
        else:
            s1 -= 1    # three-way cancellation
            s2 -= 1

    # verify — candidates may not actually be majority
    return [c for c in (c1, c2) if nums.count(c) > len(nums) // 3]

Same bones: candidates + scores, cancellation logic, survivors at the end. The only change is two candidates instead of one, and the cancellation is three-way.

num=1: s1=0  →  c1=1,s1=1
num=1: c1    →  s1=2
num=1: c1    →  s1=3
num=3: s2=0  →  c2=3,s2=1
num=3: c2    →  s2=2
num=2: neither  →  s1=2,s2=1
num=2: neither  →  s1=1,s2=0
num=2: s2=0  →  c2=2,s2=1

Candidates: c1=1 (count=3>2.67 ✅), c2=2 (count=3>2.67 ✅)
Answer: [1, 2]

Traps that catch beginners

Say it like a pro (interview one-liner)

"I'll use Moore's Voting — track one candidate and a score. Same element increases the score, different element decreases it. When score hits zero, reset the candidate. Since the majority element appears more than half the time, it can't be fully cancelled — it survives as the final candidate. One pass, O(n) time, O(1) space."

Check yourself

Practice problems

When you can solve LC #169 from memory and explain why the majority element can never be cancelled, you've learned this pattern.

Next up: Merge Intervals — a completely different flavour where we work with pairs (start, end) and learn to fold overlapping ranges into one.