Faangprep Logo
Log inStart free
Browse curriculum

Boyer-Moore Voting Algorithm

The Boyer-Moore voting algorithm finds the majority element of an array in O(N) time and O(1) space.

CANDIDATE 3 · N 7

VOTE

3

0

3

1

4

2

2

3

3

4

3

5

3

6

Candidate

3

Count

1

 

Count is 0, so 3 becomes the new candidate. Everything before this point has cancelled out exactly.

Next

3 matches the candidate → count 2.

Array

Intuition

If a majority element exists (appears > n/2 times), it will "cancel out" all other elements combined. By maintaining a candidate and a counter, we can find it in a single pass.

Concept

  • Candidate: The current potential majority element.
  • Count: A vote strength.
  • Rule: If count is 0, pick new candidate. If match, increment count. If mismatch, decrement count.

How it Works

Algorithm:

  1. Initialize candidate = null, count = 0.
  2. For each element x:
  3. If count == 0, set candidate = x, count = 1.
  4. Else if x == candidate, count++.
  5. Else count--.
  6. Return candidate.

Step-by-Step Breakdown

Watch the visualization:

  • See how the candidate changes when count hits 0.
  • Notice how the count increases/decreases based on matches.

When to Use

  • Finding the majority element (guaranteed to exist or need verification).
  • Streaming algorithms where you can't store all elements.

When NOT to Use

  • When you need exact frequencies of all elements (use Hash Map).
  • When no majority element is guaranteed (need a second pass to verify).

How to Identify

"Majority element", "Appears more than n/2 times".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Kadane's Algorithm

Next

String Basics

Frequently Asked Questions

Why does cancelling pairs find the majority element?

A majority element fills more than half the positions, so pairing each of its occurrences against a different value cannot use them all up. Every decrement cancels one majority occurrence against one non-majority occurrence, and the majority survives with a positive count.

Is the surviving candidate always the majority?

No. The algorithm only guarantees that if a majority exists, it is the candidate. When no value exceeds n/2 it still returns something, so a second pass counting the candidate is needed to confirm.

Why use it instead of a hash map?

It needs O(1) space rather than O(N). Both run in O(N) time, so the difference matters when memory is tight or the data arrives as a stream you cannot store.