Skip to content

Volume ITechnology

4.0.21 — Majority Element: the Voting Trick ​

Classic · Easy to Medium · LeetCode 169 (Majority Element), LeetCode 229 (Majority Element II)

The problem ​

Find the value that appears more than half the time in an array of length n.

[2, 2, 1, 1, 1, 2, 2]  →  2       (four 2s out of seven)

LeetCode 169 promises that such a value exists. The follow-up asks for O(n) time and O(1) extra memory.

Three answers, from simplest to best ​

1. Count everything ​

python
from collections import Counter

def majority_count(nums: list[int]) -> int:
    counts = Counter(nums)
    return max(counts, key=counts.get)

print(majority_count([2, 2, 1, 1, 1, 2, 2]))   # → 2

O(n) time, but O(n) memory for the counts.

2. Sort and take the middle ​

python
def majority_sort(nums: list[int]) -> int:
    return sorted(nums)[len(nums) // 2]

print(majority_sort([2, 2, 1, 1, 1, 2, 2]))   # → 2

Why the middle? The majority value fills more than half the array. After sorting, its copies form one solid block longer than n/2. A block that long cannot fit entirely on one side of the middle, so it must cover the middle position. This costs O(n \log n) time.

3. Boyer–Moore voting: one pass, two variables ​

Robert Boyer and J Strother Moore found this in 1981. It is short enough to memorise, and the reason it works is what the interviewer wants to hear.

The idea, as a story. Imagine an election where every voter is one array element. Two voters who support different candidates cancel each other out. They both walk away. Keep pairing off voters with different choices, until no such pair is left. Whoever is still standing must be the majority candidate. Why? The majority has more than half the voters. Even if every other voter cancels one majority voter, the majority has more voters than all the rest put together. So some majority voters are always left over.

The code does this pairing as it walks, using a candidate and a count.

python
def majority(nums: list[int]) -> int:
    candidate, count = None, 0
    for x in nums:
        if count == 0:          # (1)
            candidate = x
        if x == candidate:      # (2)
            count += 1
        else:                   # (3)
            count -= 1
    return candidate

print(majority([2, 2, 1, 1, 1, 2, 2]))   # → 2
print(majority([3, 3, 4]))               # → 3
print(majority([7]))                     # → 7

(1) No one is standing. This element becomes the new candidate.

(2) A supporter of the current candidate. One more vote.

(3) A voter for someone else. This voter and one candidate supporter cancel each other out.

Trace on [2, 2, 1, 1, 1, 2, 2]:

xcandidatecountwhat happened
221new candidate
222support
121cancel one pair
120cancel one pair
111count was 0, so 1 is the new candidate
210cancel
221new candidate

It ends with candidate 2. Notice that 1 led for a while. That is fine. The candidate in the middle of the run means nothing. Only the final one matters.

Why the final candidate must be the majority ​

Each time count drops, one candidate vote and one different vote cancel. Every cancellation removes two different values. So it can remove at most one copy of the majority value per pair.

Say the majority value appears m times, with m > n/2. The other values appear n - m times, which is fewer than m. Each cancellation that removes a majority copy uses up one non-majority copy. There are not enough non-majority copies to cancel every majority copy. So majority copies remain at the end, and the only value that can be left standing is the majority.

When the majority might not exist ​

The voting pass always returns some candidate, even for [1, 2, 3], where nobody has a majority. If the problem does not promise a majority, add a second pass that counts the candidate.

python
def majority_or_none(nums: list[int]) -> int | None:
    cand = majority(nums)
    return cand if nums.count(cand) > len(nums) // 2 else None

print(majority_or_none([1, 2, 3]))   # → None
print(majority_or_none([1, 2, 1]))   # → 1

The second pass keeps it O(n) time and O(1) memory. Forgetting it, when no majority is promised, is the classic mistake.

More than a third: two candidates ​

LeetCode 229 asks for every value that appears more than n/3 times. At most two values can do that. Three such values would need more than 3 \times n/3 = n elements in total.

So keep two candidates and two counts. A value that matches neither candidate cancels one vote from each. That is a group of three different values leaving together. Then verify both candidates with a second pass.

python
def majority_third(nums: list[int]) -> list[int]:
    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           # three different values cancel together
            n2 -= 1
    return [c for c in (c1, c2) if c is not None and nums.count(c) > len(nums) // 3]

print(majority_third([3, 2, 3]))                   # → [3]
print(majority_third([1, 1, 1, 3, 3, 2, 2, 2]))    # → [1, 2]

The order of the checks matters. First check whether x matches either candidate. Only then fill an empty slot. The other order can put the same value into both slots.

Complexity ​

MethodTimeExtra memory
CountingO(n)O(n)
Sort, take middleO(n \log n)depends on the sort
Boyer–MooreO(n)O(1)

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"Find the majority element using no extra memory." Use Boyer–Moore voting. Keep one candidate and a count. Equal values add 1. A different value takes 1 away. When the count is 0, the next value becomes the new candidate.

"Why does voting work?" Each time the count drops, two different values cancel each other out. The majority value appears more than all the others put together. So it can never be fully cancelled, and it is what remains at the end.

"What if there might be no majority?" Count how often the final candidate really appears, in a second pass. If it is not more than half, return None.

"Find every value that appears more than n/3 times." At most two values can do that. Keep two candidates and two counts, and check both at the end.

One thing to volunteer: "Voting reads each value once and keeps two variables, so it works even on data too big to fit in memory."

Next: 4.0.22 Leaders and the Equilibrium Index. Scanning from the right, and the running-sum trick that answers "left side equals right side".

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet