LeetCode #169 Medium

Majority Element

An element appears more than ⌊n/2⌋ times. Return it. (It is guaranteed to exist.)

arrayboyer-moorecounting

02

Intuition

The majority element outnumbers everything else combined. If we pair off each majority vote against one non-majority vote, the majority always has leftovers. Boyer-Moore voting exploits exactly this cancellation.

How to spot this pattern

Boyer-Moore voting. Pair off every occurrence of the majority element with a different element; because it appears more than n/2 times, it cannot be fully cancelled and whatever survives is the answer. One variable, one counter, no extra space — and the correctness argument is short enough to state in an interview, which is the point of the question.

03

Approach

1

The easy answer, and why we can do better

Counting occurrences in a hash map and returning the one above n/2 works and is O(n) time — but it uses O(n) extra space. The problem has special structure we can exploit: one element appears more than all the others combined. That strict majority is a strong promise, and it lets us solve it with two integers instead of a whole map.

2

Pair off opposites until one survivor remains

Imagine repeatedly removing two elements with different values — each removal deletes one majority element and one non-majority element at most. Because majority elements strictly outnumber everyone else, they can never be fully cancelled; some must survive. Boyer-Moore voting implements this with a candidate and a count: a matching value votes +1, a different value votes −1, and these −1s are exactly the 'cancellations.'

3

Re-elect whenever the count hits zero

Walk once. Whenever count drops to 0, the cancellations have wiped out the current candidate, so adopt the current element as the new candidate. Then apply its vote. Even if early noise installs a wrong candidate, a strict majority guarantees it gets re-elected and ends with count > 0. The final candidate is the answer — O(n) time, O(1) space.

04

Solution & live demo

▶1class Solution:
▶2    def majorityElement(self, nums):
▶3        candidate, count = None, 0
▶4        for n in nums:
▶5            if count == 0:
▶6                candidate = n
▶7            count += 1 if n == candidate else -1
▶8        return candidate

05

Common pitfalls

Counting with a hash map

✗ Wrong

counts = Counter(nums)
return max(counts, key=counts.get)

✓ Right

if count == 0: candidate = n
count += 1 if n == candidate else -1

Correct, but O(n) space where the follow-up asks for O(1). Voting achieves the same in two scalars because the majority guarantee makes cancellation safe.

Replacing the candidate whenever a different value appears

✗ Wrong

if n != candidate:
    candidate = n; count = 1

✓ Right

if count == 0:
    candidate = n
count += 1 if n == candidate else -1

The candidate only changes once its lead is fully spent. Swapping on every mismatch discards a genuine majority element the moment any other value shows up.

Assuming a majority always exists

✗ Wrong

return candidate

✓ Right

return candidate   # guaranteed by the constraints

Worth knowing the limit: the algorithm returns something even when no element exceeds n/2. This problem promises one exists — for the variant that doesn't, a second pass must verify the candidate's count.

06

Edge cases

Majority clustered at the end

Even if early non-majority votes set a wrong candidate, the trailing majority resets and re-elects itself — the count cannot survive against a strict majority.

Single element

count starts 0, the element becomes the candidate, and is returned.

Exactly ⌊n/2⌋+1 occurrences

That is still a strict majority, so cancellations leave the candidate standing.

07

Complexity

Time

O(n)

Space

O(1)

One pass; a candidate and a counter.