Boyer-Moore Majority Vote Algorithm

The Boyer-Moore Majority Vote Algorithm is an algorithm that finds the majority of a sequence of $n$ numbers $a_0,a_1,\dots ,a_{n-1}$, if the majority exists, in $\mathcal{O}(n)$ time and $\mathcal{O}(1)$ space.

Tip

This problem can also be solved by Quickselect in $\mathcal{O}(n)$ time and $\mathcal{O}(n)$ space.

Algorithm

0. Arbitrarily remove two distinct elements, until all the remaining elements have the same value.

Lemma

The value of the remaining elements is the majority of $a_0,a_1,\dots ,a_{n-1}$.

Proof

Let $c$ denote the number of occurrences of the majority in $a_0,a_1,\dots ,a_{n-1}$.

• If all the majority elements are removed, at least $c$ removes must have been performed, which implies that at least $2c$ elements are removed.

  Since

  $$c>\frac{n}{2}⟺2c>n$$

  it follows that more than $n$ elements are removed.

By contradiction, it follows that the value of the remaining elements is the majority of $a_0,a_1,\dots ,a_{n-1}$.

1. Apply the lemma to find the majority.

This algorithm solves the problem in $\mathcal{O}(n)$ time and $\mathcal{O}(1)$ space.

int boyer_moore_majority_vote(int n, const std::vector<int> &a) {
	int x = 0, c = 0;
	for (int i = 0; i < n; i++) {
		if (c) {
			c += x == a[i] ? 1 : -1;
		} else {
			x = a[i], c = 1;
		}
	}
	return x;
}