Majority Element · Optimal Solution

A candidate that survives cancellation.

In a noisy crowd, one chant dominates — more than half the voices repeat the same word. Boyer-Moore's voting algorithm finds it in a single scan: maintain a candidate and a counter. Each matching voice increments the count; each dissenting voice decrements it. When the count hits zero, switch candidates. The majority voice always survives the cancellation. O(n) time. O(1) space.

Interactive

Watch the algorithm run

Concept

Candidate and Balance

Maintain a candidate and a balance counter. When balance hits zero, adopt the current value as the new candidate. Matching values reinforce (balance++); mismatches cancel (balance−−). The true majority always survives because it can't be fully cancelled.

Algorithm

Algorithm

Boyer–Moore voting: every non-majority element cancels against a majority element. The majority survives because it has more copies than all others combined.

  1. 1

    Initialize candidate

    Set candidate = null and balance = 0. No vote has been cast yet.

  2. 2

    Vote or cancel

    For each element: if balance == 0, adopt the current value as the new candidate and set balance = 1.

  3. 3

    Increment or decrement

    If the current value matches the candidate, increment balance. Otherwise, decrement it — a cancellation.

  4. 4

    Survivor wins

    After the full scan, the candidate is the majority element. It survives because it appears more than ⌊n/2⌋ times.

Edge Cases

Edge Patterns

Understanding boundary behavior is as important as the main algorithm path.

Immediate restart

The candidate changes whenever balance drops to zero. A new candidate is adopted from the very next element — the algorithm restarts seamlessly.

Single element

An array with one element has a trivial majority. The candidate is set once and never challenged.

Complexity

Complexity

Time: O(n) — single pass.
Space: O(1) — two variables.