Majority Element

Medium · rating 1150 · arrays, algorithms

The first line contains n. The second line contains n integers. Print the element that appears more than ⌊n/2⌋ times (guaranteed to exist).

Editorial

Approach (Boyer–Moore voting)

Keep a candidate and a counter. For each element: if the counter is 0, adopt the element as the new candidate; then increment the counter if it matches the candidate, else decrement. The element appearing more than n/2 times survives.

Why it works

Pairing each majority element with a different element cancels both out. Since the majority occurs more than half the time it can't be fully cancelled, so whatever remains is the answer.

count = 0; cand = None
for x in nums:
    if count == 0: cand = x
    count += 1 if x == cand else -1
return cand

Complexity

Time: O(n). Space: O(1).

Open Majority Element in Code Arena →