Majority Element — Algorithmics

One value appears more than $n/2$ times. Find it.

majorityElement([]int{2, 2, 1, 1, 1, 2, 2})   // 2

The two answers you already know

Count with a map. $O(n)$ time, $O(n)$ space. Correct, obvious, and the sensible default.

Sort and take the middle. A value occupying more than half the positions must cover index $n/2$ whatever else is there. $O(n \log n)$ , one line, and a nice argument.

Both are fine. The reason this problem is famous is a third answer that uses no extra memory at all.

Boyer-Moore voting

Hold one candidate and one counter. Walk the array. Matching values vote for the candidate, differing values vote against, and when the count hits zero the next value becomes the new candidate.

Index 1 / 7

▾ 2 0

2 1

1 2

1 3

1 4

2 5

2 6

candidate

count

The count had hit zero, so everything before this point cancelled out exactly. Whatever the majority is, it is still the majority of what remains — so 2 becomes the new candidate.

func majorityElement(nums []int) int {
    candidate := 0
    count := 0

    for _, v := range nums {
        if count == 0 {
            candidate = v
        }

        if candidate == v {
            count++
        } else {
            count--
        }
    }

    return candidate
}

$O(n)$ time, $O(1)$ space, one pass.

The promise it depends on

With no majority, it returns a confident wrong answer

majorityElement([]int{1, 2, 3})   // 3 — and there is no majority at all

The pairing argument assumes a value that cannot be cancelled. Remove that assumption and the algorithm still returns something, with no signal that the something is meaningless.

LeetCode guarantees a majority exists, so this passes. Outside that guarantee, Boyer-Moore is a candidate finder, not an answer — and it needs a second pass to confirm:

count = 0
for _, v := range nums {
    if v == candidate {
        count++
    }
}
if count <= len(nums)/2 {
    return -1        // no majority
}

Still $O(n)$ and $O(1)$ . Write it whenever the guarantee is not in the problem statement, and be suspicious of any solution whose correctness lives in a sentence you were told rather than in the code.

Generalising to n/3

The same idea extends: at most two values can appear more than $n/3$ times, so track two candidates and two counters. More than $n/k$ needs $k-1$ of each — the Misra–Gries algorithm, and Boyer-Moore is its $k = 2$ case.

That generalisation is where it stops being a puzzle and starts being useful. Finding heavy hitters in a stream — the IPs sending the most traffic, the products bought most often — is exactly this, run over data far too large to count exactly.