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
def majorityElement(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 tallies every value’s frequency; the majority is the key with the largest tally. Trade space for time.
from collections import Counter
from typing import List
def majorityElement(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
def majorityElement(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. Each cancellation removes 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, which finds a strict-majority value in one pass with constant memory.
from typing import List
def majorityElement(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, leaving one candidate and one counter. Boyer–Moore is the standard “guaranteed-majority ⇒ O(1) space” upgrade, valid only under that precondition.