Element repeated more than n/2 times – Fast majority vote algorithm

Find the element which repeated more than n/2 times in an given array of integers.

For example, A=[2, 2, 3, 2, 3, 3, 1, 3, 1]. We can clearly see that 3 is the majority.

A quick an dirty solution would be to either use a Hashmap to count frequency of each element and keep the track of maximum frequency element. This is O(n) time algorithm but it takes O(n) space. Another trivial solution would be to sort the array in O(nlgn) and then make a O(n) pass to the sorted array to find the maximum occurring element. This is O(nlgn) algorithm.

But there is an intelligent, beautiful, and efficient (both time and space) solution to this problem based on the solution of a real life scenario where voters are voting for their candidates. Assume that number of candidates is not fixed or not known beforehand. Also suppose that there are n voters each carrying a placard with the name of his candidate. Their is a chairman who is counting the vote. The chairman devised a simple method to keep track of the majority vote candidate C and a counter K which is initialized to zero. Each time the chairman goes to a voter and see if K=0; If it is then he keep n mind that C=candidate of the current voter and sets K=1. If K!=0 then he sees whether the voter holds placard for the current majority candidate C. If yes then he increases the counter K otherwise decreases it. He keeps counting by going to next voter and so on. So, once the chairman has visited all the voters the the C would be the majority vote candidate. This is because as long as one candidate got at least n/2 votes, we can guarantee that this approach will always find the majority element.

For a full correctness proof, citation to the original paper (by Boyer and Moore of the more famous Boyer-Moore string matching algorithm), check out this link.

This is only O(n) time and O(1) space in-place algorithm. Below is a simple implementation.

public int majorityVoteCandidate(final int[] votes) {
    int c = votes[0];
    int k = 1;

    for (int i = 1; i < votes.length; i++) {
        if (votes[i] == c) {
            k++;
        } else {
            k--;
            if (k == 0) {
                c = votes[i];
                k = 1;
            }
        }
    }
    return c;
}