Faangprep Logo
LoginRegister
Browse Curriculum

Boyer-Moore Voting Algorithm

Visualize finding the Majority Element in O(N) time and O(1) space.

Candidate

-

Count

0

Ready to find Majority Element.
2
0
2
1
1
2
1
3
1
4
2
5
2
6
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.
Unlock VisualizerPREMIUM FEATURE

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

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep