Majority Element

ARRAYS & HASHING · EASY

The problem

Given an array nums of size n, find the majority element — the one value that appears more than ⌊n/2⌋ times. The problem guarantees a majority element always exists, so you never have to handle the “no winner” case. For example, [3,2,3] has n=3, so a value needs to appear more than 1 time — 3 appears twice and wins. Likewise [2,2,1,1,1,2,2] has n=7, needs more than 3 occurrences, and 2 appears 4 times.

Solution 1: Brute force — hash-map frequency counting

The direct approach: walk the array once and build a frequency map — for every value seen, increment its count by one. Once every value’s count is known, scan the map’s entries for the one whose count clears the ⌊n/2⌋ bar. This is completely correct and needs no cleverness, but it pays for a second data structure the size of the input.

function majorityElementBruteForce(nums) {
  const freq = new Map();
  for (const v of nums) {
    freq.set(v, (freq.get(v) || 0) + 1);
  }

  const n = nums.length;
  for (const [value, count] of freq) {
    if (count > Math.floor(n / 2)) return value;
  }
  return null; // unreachable — the problem guarantees a majority element exists
}

Line by line:

freq is a Map, not a plain object — every distinct value in nums becomes its own key, and Map compares keys by identity/value without the string-coercion quirks a plain object has (more on that in Interview Corner below).
The first loop is a single O(n) pass: for every element, look up its current count (defaulting to 0 the first time it’s seen) and increment it by one.
The second loop scans the finished map’s entries — at most n distinct keys — and returns the first value whose count strictly exceeds ⌊n/2⌋.
The final return null is unreachable for any input that satisfies the problem’s guarantee; it only exists so the function has a defined fallback.

Interactive visualization

nums = [2, 1, 2, 3, 2, 4, 2] — majority element is 2, count 4 > 3

Press play to run the brute force algorithm.

approach: scan once, count every value

Step 0 / 9

This animation traces nums=[2,1,2,3,2,4,2] — the majority element (2) is neither first-only nor contiguous; it’s also the last element, verified above.

Complexity

Time	Space	Approach
O(n)	O(n)	Hash-map frequency count, then scan the map

Solution 2: Optimal — Boyer-Moore Voting Algorithm

Track just two variables: a candidate and a count. Walk the array once. Whenever count is 0, the current element becomes the new candidate. Then, if the current element equals the candidate, increment count; otherwise decrement it. After one pass, candidate holds the majority element — no map, no extra array, just two numbers.

Why this actually works: think of every element that matches the current candidate as a +1 vote and every element that doesn’t as a −1 vote against it. A mismatch and a match cancel each other out one-for-one in count. Because the true majority element appears MORE than n/2 times, it outnumbers every other value combined — even in the worst case where every single non-majority element gets paired up against it to cancel a vote, there aren’t enough non-majority elements to cancel all of the majority’s votes. So the majority element can never be fully “voted off” — it always survives as the final candidate, possibly after a few false candidates get knocked out to 0 along the way.

This correctness genuinely depends on the guarantee. If no true majority element exists, Boyer-Moore Voting still runs and still produces SOME candidate — but that candidate is not necessarily an actual majority element, and the algorithm gives no signal that anything went wrong. For example, tracing this exact algorithm on [1, 2, 3, 4] (no value appears more than twice, let alone more than n/2 = 2 times) ends with candidate = 3 — a value that occurs exactly once. Without the problem’s guarantee, a real solution would need a second verification pass (count the final candidate’s actual occurrences and check it against n/2) before trusting the result. LeetCode’s guarantee is exactly what licenses skipping that verification pass here.

function majorityElementOptimal(nums) {
  let candidate = null;
  let count = 0;

  for (const v of nums) {
    if (count === 0) {
      candidate = v;
    }
    count += (v === candidate) ? 1 : -1;
  }

  return candidate; // guaranteed correct ONLY because a true majority is guaranteed to exist
}

Line by line:

candidate and count are the algorithm’s entire state — no array, no map, O(1) extra space regardless of input size.
if (count === 0) candidate = v; — whenever the running tally has fully cancelled out, throw away whatever candidate was losing and give the current element a fresh start.
count += (v === candidate) ? 1 : -1; — this runs on EVERY element, including the one that was just adopted as the new candidate (which always increments, since it trivially matches itself).
After the loop, candidate is returned directly — there’s no final verification step here, which is exactly the shortcut the problem’s guarantee licenses.

Interactive visualization

nums = [2, 7, 2, 1, 7, 7, 7, 3, 7] — majority element is 7, candidate changes from 2 to 7 partway through

Press play to run the Boyer-Moore Voting Algorithm.

approach: one pass, two variables

Step 0 / 14

This animation traces nums=[2,7,2,1,7,7,7,3,7] — the candidate flips from 2 to 7 partway through, which is exactly the behavior worth watching closely, verified above.

Complexity

Time	Space	Approach
O(n)	O(1)	Boyer-Moore Voting — single pass, two variables

Complexity comparison

Solution	Time	Space
Brute force (hash-map frequency count)	O(n)	O(n)
Optimal (Boyer-Moore Voting)	O(n)	O(1)

Both solutions are O(n) time — there is no asymptotic speedup here, and it would be dishonest to claim one. The real, honest improvement Boyer-Moore offers is space: it drops the O(n) frequency map down to O(1), two plain variables that don’t grow with the input.

Interview corner

Why does the Boyer-Moore Voting Algorithm actually converge on the true majority element, instead of just being a heuristic that happens to work?

Model it as a cancellation game: every element that doesn’t match the current candidate cancels exactly one “vote” from it (count--); every match adds one (count++).
A true majority element appears more than n/2 times — strictly more than every other value in the array COMBINED.
Even in the worst case, where every single non-majority element gets used to cancel a majority vote, there simply aren’t enough non-majority elements to cancel all of them. At least one majority vote always survives, which is exactly why it’s the value left standing as candidate at the end.

What is the actual, honest complexity improvement of Boyer-Moore over the hash-map brute force — and what would be dishonest to claim?

Both solutions are O(n) TIME — one pass over the array either way. Claiming Boyer-Moore is “faster” in the Big-O sense would be incorrect.
The real difference is SPACE: the hash map is O(n) because it can grow to hold one entry per distinct value, while Boyer-Moore is O(1) — just candidate and count, regardless of how large nums is.
In an interview, stating this precisely (space improvement, not time) signals more rigor than a vague “it’s more optimal.”

What happens if you run this exact algorithm on an array that does NOT have a true majority element — and how would you make the solution robust to that case?

The algorithm doesn’t detect the absence of a majority — it still runs to completion and returns SOME candidate value, with no error and no signal that the result is meaningless.
For example, on [1, 2, 3, 4] — where nothing appears more than ⌊4/2⌋ = 2 times — this exact algorithm ends with candidate = 3, which occurs only once and is not a majority element at all.
To make it robust without the guarantee: add a second O(n) pass after the loop that actually counts candidate’s occurrences and checks it against n/2 before trusting it. Still O(n) time and O(1) extra space overall.

↳ Common follow-up: “Does this problem’s guarantee actually matter, or is it just flavor text?” It matters a lot — it’s the entire reason the single-pass version without verification is allowed to be correct here.

Trick question — what does this log?

const counts = {};
counts[1] = 'from number key';
counts['1'] = 'from string key';
console.log(Object.keys(counts).length);
console.log(counts[1] === counts['1']);

Answer: 1, then true — not 2 and false.

Plain object keys are always coerced to strings. counts[1] and counts['1'] are the exact same key — the second assignment silently overwrites the first. A Map has no such coercion: map.set(1, ...) and map.set('1', ...) are two genuinely distinct entries, and map.size would correctly report 2.

⚠ Trap: this is exactly why the brute-force solution above uses a Map for freq instead of a plain {}. This particular problem only ever sees numeric values, so the collision wouldn’t actually bite here — but the same frequency-counting pattern shows up constantly for problems mixing numbers and strings (or object keys), where a plain object would silently merge two distinct values into one count.

Quiz

1. Why does Boyer-Moore Voting correctly find the majority element when the input is guaranteed to have one?

Because the majority’s more-than-n/2 occurrences can never be fully cancelled out by every other value combined
Because the algorithm secretly sorts the array first
It only works by coincidence on small arrays

2. What is the real, honest complexity improvement of the optimal solution over the brute-force hash-map solution?

Space only — both are O(n) time, but space drops from O(n) to O(1)
Time only — the optimal solution is asymptotically faster than O(n)
Both time and space improve by a full order of magnitude

3. What happens if you run the unmodified Boyer-Moore algorithm on an array with NO true majority element, such as [1, 2, 3, 4]?

It still returns some candidate value, but that value is not guaranteed to actually be a majority element
It throws a runtime error since count would go negative
It always correctly returns null in that case

4. In the Boyer-Moore trace, what causes the candidate variable to change value partway through the array?

The running count reaches 0 — the current candidate has been fully cancelled out, so a new one is adopted
It changes automatically every 10 elements regardless of the count
Only after the array is internally re-sorted

5. Why does the brute-force solution use a Map instead of a plain JavaScript object to store frequency counts?

Plain object keys get coerced to strings, which can silently collide two distinct values into one count — Map avoids that
Map is always significantly faster to read from than a plain object
Plain objects can’t store numeric values at all