Arrays & Hashing crash course ↗ · 165

169. Majority Element

One value appears more than n/2 times. Instead of counting everything, Boyer–Moore voting keeps a single candidate and a count: matches vote it up, mismatches cancel it out, and the true majority always survives — O(n) time, O(1) space.

● EasyBoyer-Moore VotingHash MapTypeScript

PROBLEM What we're solving

Given an array nums of size n, return the element that appears more than ⌊n/2⌋ times. You may assume it always exists. nums = [2,2,1,1,1,2,2] → 2 (it appears 4 times, and 4 > 7/2).

KEY IDEA A majority beats everyone else combined

Insight → if one value occurs more than half the time, then pairing each majority element with one non-majority element still leaves majority elements left over. So if you let every matching element add a vote and every differing element cancel a vote, the minority votes can never fully erase the majority. Whoever is holding the lead when the scan ends is the answer.

RECIPE Adopt, vote, survive

  • 0 · Init. count = 0, no committed candidate yet.
  • 1 · Adopt when empty. When count === 0, take the current value as the new candidate— the old one has been fully cancelled out, so start fresh.
  • 2 · Vote. If the value equals the candidate, count++; otherwise count--.
  • 3 · Return. After one pass, the surviving candidate is the majority element.
Classic confusion → the candidate doeschange mid-scan, and at any moment it might not be the true majority. That's fine — the algorithm only guarantees the finalcandidate is correct, and only when a majority is guaranteed to exist. If existence isn't guaranteed, you must verify with a second counting pass.

COST Complexity & alternatives

Hash-map counts
O(n) space
O(n) time, but an extra map of frequencies.
Boyer–Moore voting
O(1) space
One pass, two scalars, no extra structure.

Space note

Counting with a Map is the obvious O(n)-time approach but it stores up to n distinct keys. Voting keeps only candidate and count, so it is O(1) space — the reason it's the textbook answer.

Pattern transfer → the same cancellation idea generalizes to Majority Element II (elements > n/3, tracked with twocandidates) and any "survives the pairwise cancellation" argument.

RUN IT Cancel out the minority, the majority survives

step 0 / 11
STARTBoyer–Moore voting: start with no candidate and count = 0.
1function majorityElement(nums: number[]): number {
2▶  let candidate = 0;
3▶  let count = 0;
4 
5  for (const x of nums) {
6    if (count === 0) candidate = x;   // adopt a fresh candidate
7    count += x === candidate ? 1 : -1; // vote with it or against it
8  }
9 
10  return candidate; // the > n/2 element always survives
11}
nums20211213142526
State
—
candidate
0
count
adopt candidatevote +1vote −1processed
slowfast

TYPESCRIPT The solution, annotated

majorityElement.ts
function majorityElement(nums: number[]): number {
  let candidate = 0;
  let count = 0;

  for (const x of nums) {
    if (count === 0) candidate = x;    // adopt a fresh candidate
    count += x === candidate ? 1 : -1; // vote with it or against it
  }

  return candidate; // the > n/2 element always survives
}

Reading it block by block

Lines 2–3 — state. A single candidate and an integer count. The initial candidate value is irrelevant because count starts at 0, forcing an adoption on the first element.
Line 6 — adopt when neutral. When count === 0 the current candidate has been fully cancelled, so we commit to the value in front of us as the new candidate.
Line 7 — cast a vote. Matching the candidate pushes count up; anything else pushes it down. Minority elements can drain it to 0but never below the majority's surplus.
Line 10 — the survivor. Because the majority outnumbers everyone else combined, it is mathematically impossible for its votes to be fully cancelled, so the final candidate is the answer.
Complexity → O(n) time (one linear pass), O(1) space (two scalars). Optimal — you must read every element at least once.

INTERVIEWFollow-ups they'll ask

  • "What if a majority isn't guaranteed?"Run a second pass to confirm the candidate actually appears > n/2 times; otherwise report none.
  • "Elements appearing more than n/3 times?" Majority Element II: track two candidates and two counts (at most two values can exceed n/3).
  • "Why does the candidate flip mid-scan?" Only the final result is guaranteed correct; intermediate candidates may be wrong, which is acceptable.
  • "Other ways to do it?" Hash-map counting (O(n) space), sorting and taking nums[n/2] (O(n log n)), or a randomized pick-and-verify.

OPTIMAL Boyer-Moore Voting

majorityElement.ts
function majorityElement(nums: number[]): number {
  let candidate = 0;
  let count = 0;

  for (const x of nums) {
    if (count === 0) candidate = x;    // adopt a fresh candidate
    count += x === candidate ? 1 : -1; // vote with it or against it
  }

  return candidate; // the > n/2 element always survives
}
Complexity → O(n) time (one linear pass), O(1) space (two scalars). Optimal — you must read every element at least once.

ALT 1 Hash-map counting

O(n) time · O(n) space

The brute-force default: tally every value's frequency in a Map, then return whichever key crosses n/2.

approach-2.ts
function majorityElement(nums: number[]): number {
  const counts = new Map<number, number>();
  for (const x of nums) {
    const c = (counts.get(x) ?? 0) + 1;
    if (c > nums.length / 2) return x;
    counts.set(x, c);
  }
  return nums[0]; // majority guaranteed to exist
}
Note → Easy to reason about, but it allocates a map of up to ndistinct keys — O(n) space. Boyer–Moore voting reaches the same answer with two scalars and O(1) space.

ALT 2 Sort and take the middle

O(n log n) time · O(1) space

If a value occupies more than half the array, after sorting it must cover the middle index, so nums[⌊n/2⌋] is the answer.

approach-3.ts
function majorityElement(nums: number[]): number {
  nums.sort((a, b) => a - b);
  return nums[Math.floor(nums.length / 2)];
}
Note → A neat one-liner, but sorting dominates at O(n log n) and mutates the input. Voting stays linear.

MNEMONIC The one-liner

"Empty? adopt. Match? +1. Differ? −1. The majority can't be cancelled out."

TRIGGERS When you see ___ → reach for ___

"element appears > n/2 times"Boyer–Moore voting
find the majority in O(1) spacecandidate + count
count hits zeroadopt the current value
"> n/3 times" / two majoritiestwo candidates (Majority II)

SKELETON The reusable shape

skeleton.ts
let candidate = 0;
let count = 0;
for (const x of nums) {
  if (count === 0) candidate = x;
  count += x === candidate ? 1 : -1;
}
return candidate;

FLASHCARDS Tap to flip

Core invariant of Boyer–Moore voting?
count tracks (votes for candidate) − (votes against). The majority can never be fully cancelled.
tap to flip
1 / 6
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
Optimal space complexity of Boyer–Moore voting?
QUESTION 02
When does the algorithm pick a new candidate?
QUESTION 03
How is count updated for each element x?
QUESTION 04
Why is the final candidate guaranteed to be the majority?
QUESTION 05
For nums = [2,2,1,1,1,2,2], the answer is:
QUESTION 06
If a majority element is NOT guaranteed to exist, what must you add?
QUESTION 07
Which problem extends this exact cancellation idea to elements appearing > n/3 times?
QUESTION 08
#169 · Majority ElementFind the element appearing more than n/2 times in O(n) time and O(1) space with the Boyer-Moore voting algorithm: a single candidate and a count that cancels out every minority vote, leaving the majority standing.Which algorithmic approach does this primarily use?
QUESTION 09
#169 · Majority ElementFind the element appearing more than n/2 times in O(n) time and O(1) space with the Boyer-Moore voting algorithm: a single candidate and a count that cancels out every minority vote, leaving the majority standing.Which implementation correctly solves it?