TL;DR
Boyer–Moore majority voting — O(n) time, O(1) space.
Approach 1 — Brute force
Count each value’s occurrences with a fresh scan and return the one exceeding n/2.
from typing import List
class Solution:
def majorityElement(self, nums: List[int]) -> int:
n = len(nums)
for x in nums:
count = 0
for y in nums:
if y == x:
count += 1
if count > n // 2:
return x
return -1 # unreachable: a majority is guaranteed
Complexity: O(n²) time, O(1) space.
At n = 5·10^4 that’s ~2.5 billion comparisons — far too slow.
Approach 2 — Hash map of counts
The insight: one pass can tally every value’s frequency; the majority is just the key with the biggest tally. This is the default Arrays & Hashing move: trade space for time.
from collections import Counter
from typing import List
class Solution:
def majorityElement(self, nums: List[int]) -> int:
counts = Counter(nums)
best = max(counts, key=counts.get)
return best
Walkthrough on nums = [2, 2, 1, 1, 1, 2, 2]: the Counter ends as {2: 4, 1: 3}; the key with the maximum count is 2 → return 2.
Complexity: O(n) time, O(n) space in the worst case (up to n/2 distinct keys plus the majority).
Approach 3 — Sorting
The insight: a value occupying more than half the slots of a sorted array must cover the middle index — its run of equal values is longer than half the array, so no placement can avoid position ⌊n/2⌋.
from typing import List
class Solution:
def majorityElement(self, nums: List[int]) -> int:
nums.sort()
return nums[len(nums) // 2]
Walkthrough on [2, 2, 1, 1, 1, 2, 2]: sorted it becomes [1, 1, 1, 2, 2, 2, 2]; the middle index is 3, and the element there is 2.
Complexity: O(n log n) time, O(1) extra space (in-place sort). Two lines, but not yet the follow-up’s O(n).
Approach 4 — Boyer–Moore voting
The insight: occurrences of the majority element outnumber all other elements combined. So let elements “cancel” each other: keep one candidate and a counter; a matching element votes +1, a differing element votes −1, and when the counter hits zero adopt the next element as the new candidate. Every cancellation destroys at most one majority occurrence together with one non-majority occurrence, so the majority always survives to the end. This is the Boyer–Moore majority vote algorithm, a classic streaming algorithm that finds a strict-majority value in one pass with constant memory.
from typing import List
class Solution:
def majorityElement(self, nums: List[int]) -> int:
candidate = nums[0]
count = 0
for x in nums:
if count == 0:
candidate = x
if x == candidate:
count += 1
else:
count -= 1
return candidate
Walkthrough on nums = [2, 2, 1, 1, 1, 2, 2]:
| x | count == 0? | candidate | count after |
|---|
| 2 | yes → adopt 2 | 2 | 1 |
| 2 | no | 2 | 2 |
| 1 | no | 2 | 1 |
| 1 | no | 2 | 0 |
| 1 | yes → adopt 1 | 1 | 1 |
| 2 | no | 1 | 0 |
| 2 | yes → adopt 2 | 2 | 1 |
Final candidate: 2 — correct, even though the candidate changed twice along the way.
Complexity: O(n) time, O(1) space — meets the follow-up exactly.
Common pitfalls
- Boyer–Moore returns the right answer only because a majority is guaranteed. If the guarantee is absent (see Majority Element II or arbitrary inputs), you must add a second verification pass that re-counts the candidate.
- Using
>= n/2 instead of strictly > n/2 when verifying — “majority” means strictly more than half.
- In the voting loop, decrementing without ever re-adopting a candidate when the count returns to zero — the adoption step is what makes the cancellation argument work.
- Assuming the majority sits at the middle of the unsorted array — the middle-index trick is valid only after sorting.
Pattern takeaway
Frequency questions start with a hash map — O(n) time, O(n) space, always correct. But when the target is guaranteed to dominate (strictly more than half), pairwise cancellation lets you drop the map entirely: one candidate and one counter survive any sequence of cancellations. Remember Boyer–Moore as the canonical “guaranteed-majority ⇒ O(1) space” upgrade, and remember its precondition.