Boyer-Moore Majority Vote Algorithm

Posted on | In

Boyer-Moore Majority Vote Algorithm finds the majority of a sequence of elements if there is one. Note that if there is no majority, the algorithm cannot detect it.

The algorithm

How does the algorithm work? The idea is to keep a counter for the majority.

1
2
3
4
5
6
7
8
9
10
11
12
int counter = 0;
int number;
for (int i = 0; i < sequence.length; i++) {
    if (counter == 0) {
        number = sequence[0];
        counter++;
    } else {
        if (sequence[i] == number) counter++;
        else counter--;
    }
}
return number;

This can be found on leetcode: 169. Majority Element

More

The problem is now to find all elements that appear more than n/3: 229. Majority Element II.

Because the element must appear more than n/3, there should be one or two of such elements. We can keep two counters. Both counters deduce 1 when the current number is not the majority.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int counter1 = 0, counter2 = 0;
int number1, number2;
for (int i = 0; i < sequence.length; i++) {
    if (counter1 > 0 && number1 == sequence[i]) {
        counter1++;
    } else if (counter2 > 0 && number2 == sequence[i]) {
        counter2++;
    } else if (counter1 == 0) {
        number1 = sequence[i];
        counter1++；
    } else if (counter2 == 0) {
        number2 = sequence[i];
        counter2++;
    } else {
        counter1--;
        counter2--;
    }
}

But this is not enough, either number1 or number2 might not be the majority, so we should make a second pass through the sequence to verify if number1 or number 2 is the majority.

Note that this algorithm can be applied to the cases where the majority appears more than n/k.

References

1 wikipedia
2 Proof of correctness of the algorithm: the first answer looks correct