You're handed an array nums of n integers, and one value is the undisputed majority — it appears more than ⌊n / 2⌋ times, so it fills over half the array. Return that value.
You may assume the majority element always exists, so you never have to handle a 'no winner' case.
For nums = [2, 2, 1, 1, 1, 2, 2] we have n = 7, so half is 3. The value 2 shows up 4 times — strictly more than half — so the answer is 2.
Input: nums = [3,2,3] Output: 3 n = 3, so half is 1. The value 3 appears 2 times — more than half.
Input: nums = [2,2,1,1,1,2,2] Output: 2 n = 7, so half is 3. The value 2 appears 4 times — more than half.
- n == nums.length - 1 <= n <= 5 * 10^4 - -10^9 <= nums[i] <= 10^9 - The input is generated such that a majority element always exists in the array.
Majority Element is the gateway to Boyer–Moore voting — one of those algorithms that feels like a magic trick until you see the invariant, then feels inevitable. One value fills more than half the array; the art is surfacing it in a single pass with two integer variables and no memory.
n/2 times. The hash-map approach counts this directly.O(1) state: a current guess and how many "net votes" back it.Given an array nums where one value appears more than ⌊n/2⌋ times, return that value. You may assume the majority always exists.
Worked example — nums = [2, 2, 1, 1, 1, 2, 2]
val 2 → candidate 2, count 1 val 2 → same, count 2 val 1 → diff, count 1 val 1 → diff, count 0 val 1 → count 0 → adopt 1, count 1 val 2 → diff, count 0 val 2 → count 0 → adopt 2, count 1 survivor: 2 ✓
“Is a majority element guaranteed to exist?”
Yes here — so you can trust the survivor without verifying. If it weren't guaranteed, you'd add a second pass to confirm the candidate really exceeds n/2.
“Is 'majority' strictly more than n/2, or at least half?”
Strictly more than ⌊n/2⌋ — that strictness is exactly why cancellation can't eliminate it.
“Does the majority's position in the array matter?”
No — only its count. It can be scattered anywhere; the vote survives regardless of order.
“What about a single-element array?”
That element is trivially the majority.
“Return the value or its count/index?”
The value itself.
“How large can the array be?”
Up to 5×10⁴. An O(n²) recount (~10⁹ ops) risks timing out; Boyer–Moore is O(n) time and O(1) space.
A couple of questions.
Is a majority element guaranteed to exist, so I don't need a verification pass?
Majority means strictly more than n/2 occurrences?
I'll do it in O(n) time and O(1) space with Boyer–Moore voting.
Imagine repeatedly deleting a pair of different values. Each deletion removes at most one majority vote, and there are fewer than n/2 non-majority votes to pair against. They run out first, so at least one majority vote always remains. That's the whole engine.
You don't need to actually delete elements. Keep a candidate and a count: the same value strengthens the candidate (count++), a different value cancels one (count--), and when count hits 0 you adopt the current value as the new candidate. The candidate left standing at the end is the majority.
Boyer–Moore always returns some candidate, even on an array with no majority. When existence isn't promised, run a second pass to count the candidate and confirm it truly exceeds n/2 before trusting it.
| Recount each candidate | Hash map tally | Boyer–Moore | |
|---|---|---|---|
| Idea | Count every value's occurrences | One-pass frequency map | Cancellation with candidate + count |
| Time | O(n²) | O(n) | O(n) |
| Space | O(1) | O(n) | O(1) |
The full code for all three is in the Approaches selector below.
Key takeaway
Boyer–Moore voting finds a strict majority in one pass with O(1) space: keep a candidate and a count, strengthen on a match, cancel on a mismatch, and adopt a new candidate when the count hits zero. It works because a value appearing more than n/2 times can never be fully cancelled by the fewer-than-n/2 others.