Majority Element

Problem. Find the element appearing more than $n/2$ times in an array, if one exists.

Boyer-Moore voting — $O(n)$ time, $O(1)$ space

int majority(const vector<int>& a) {
    int cand = a[0], count = 0;
    for (int x : a) {
        if (count == 0) cand = x;
        count += (x == cand) ? 1 : -1;
    }
    // VERIFY — a majority may not exist
    int c = 0;
    for (int x : a) if (x == cand) c++;
    return c * 2 > (int)a.size() ? cand : -1;
}

The intuition: pair each occurrence of the candidate with a non-occurrence and cancel them. A true majority element survives every cancellation, because it has more copies than everything else combined.

Always verify

The algorithm returns some element even when no majority exists. The second pass is not optional. This is the most common mistake with this algorithm.

See Boyer-Moore Voting.

The generalisation: elements appearing more than $n/k$ times

At most $k-1$ such elements exist. Keep $k-1$ candidates with counts; when a new element matches none and all counters are non-zero, decrement all of them.

vector<int> majorityK(const vector<int>& a, int k) {
    map<int,int> cnt;                                  // at most k-1 entries
    for (int x : a) {
        if (cnt.count(x)) cnt[x]++;
        else if ((int)cnt.size() < k - 1) cnt[x] = 1;
        else {
            for (auto it = cnt.begin(); it != cnt.end(); )
                if (--it->second == 0) it = cnt.erase(it); else ++it;
        }
    }
    // verify each candidate with a second pass
    vector<int> res;
    for (auto& [v, _] : cnt) {
        int c = count(a.begin(), a.end(), v);
        if (c * k > (int)a.size()) res.push_back(v);
    }
    return res;
}

$O(nk)$ time, $O(k)$ space. This is the Misra-Gries algorithm, and it is the standard streaming “heavy hitters” primitive.

The alternatives

Method	Time	Space	Note
Boyer-Moore voting	$O(n)$	$O(1)$	optimal; needs verification
Hash map counting	$O(n)$	$O(n)$	simplest; also gives all counts
Sort, take the middle	$O(n\log n)$	$O(1)$	the majority must occupy index $n/2$
Randomised sampling	$O(n)$ expected	$O(1)$	pick a random element, verify; succeeds with probability $>1/2$
Bit-by-bit majority	$O(n\log C)$	$O(1)$	for each bit, take the majority bit
Divide and conquer	$O(n\log n)$	$O(\log n)$	the majority of the whole is a majority of some half

The sort-and-take-the-middle observation is worth remembering: if an element occupies more than half the array, it must cover position $n/2$ after sorting. One line, if a sort is affordable.

Range majority queries

“What is the majority element of $a[l..r]$?” — harder, and there are several routes:

Method	Cost
Randomised: sample $O(\log n)$ positions in the range and verify each	$O({\log }^{2}n)$ per query, high probability
Segment tree with Boyer-Moore merge	$O(\log n)$ per query + verification
Persistent segment tree over values	$O(\log n)$, exact
Mo’s algorithm	$O(n\sqrt{n})$

The segment tree merge works because the Boyer-Moore pair (candidate, count) is mergeable: combining two ranges’ candidates cancels the smaller count. Verification still requires counting occurrences, typically with a sorted position list per value plus binary search.

Streaming relatives

Problem	Algorithm	Space
Majority	Boyer-Moore	$O(1)$
Elements $>n/k$	Misra-Gries	$O(k)$
Approximate frequencies	Count-Min sketch	$O(1/\epsilon )$
Distinct count	HyperLogLog	$O(\log \log n)$
Uniform sample	reservoir sampling	$O(k)$

Why it is worth knowing

Boyer-Moore voting is the cleanest example of a cancellation argument: the answer survives because it outnumbers everything else combined. That framing — pair up and cancel — appears in parity arguments, in XOR tricks for “find the unique element”, and in several streaming algorithms.

See also: Boyer-Moore Voting · Reservoir Sampling · Segment Tree