Moore's Voting Algorithm

We always do a lot of programming problems just to hone our programming skills But those problems are most of the time puzzles. Very recently +Vinay Singh  came up to me with a fairly simple but a different problem( at least at first i thought it was simple) and i did it in O(n) time complexity and O(n) auxiliary space complexity(straightaway complexities no way...:P) it hardly took me 10 minutes to reach the solution.

The fun part starts after that when he added a constraint to the problem that i had to do it in auxiliary space O(1). For people who are not aware of auxiliary space it is using extra memory while designing an algorithm and now the constraint meant i had to do it without using any extra memory.

So first of all let me walk you through the Problem statement:-

There are N number of voters in a hall who are going to choose a leader by the process of voting, the person with the majority of votes wins. Majority is when a person has number of votes more than the half of the total votes. So the problem is to find out the person who has the majority given the votes casted by the voters in an array.

FIRST SOLUTION #easyone

The first and obvious solution to this problem is to have two loops and keep track of maximum count for all different elements. If maximum count becomes greater than n/2 then break the loops and return the element having maximum count. If maximum count is less than n/2 then majority doesn't exist and we are in trouble.

Problem with this solution is it sucks at time complexity O(n*n) for nested for loop.
Space complexity O(1)  umm okay....:)

SECOND SOLUTION #alsoeasy

This was the approach i followed, i used an array to keep track of the count of every vote that was casted and incremented the counts, if at any point the incremented count exceeded half the number of votes we get a majority and break the loop.

int[] count = new int[cast.length];  
// cast array is votes casted
int count1, num;
for(int i=0; i<cast.length; i++) {
    num = ++count[cast[i]];   
    // increments count on vote cast in array
    if(num > cast.length/2) {
        System.out.println("Winner is candidate " +cast[i]);  
        // returns the index of winner
	break;
    }
}

Time complexity O(n)
but, space complexity O(n) disappointment in the end.

THIRD SOLUTION #moore's algo

This is a real classic believe me!!!
The basic idea behind this algorithm is if we cancel each occurrence of an element 'e' with all the other elements that are different from 'e', In this process 'e' will exist till the end if its the majority element(occurs more than n/2 times).

int count = 1, majorityIndex = 0;
for(int i=1; i<cast.length; i++) {
    if(cast[i]==cast[majorityIndex])
        count++;
    else
	count--;
    if(count==0) { // no majority at this point
	majorityIndex=i;
	count=1;
    }
}
System.out.println("Majority element is " + cast[majorityIndex]);

A very nice example showing different passes of this algorithm.

LIMITATION OF MOORE'S ALGORITHM

I was searching for this particular algorithm on web when i came across this question on stack overflow.
From this question we can clearly find out that for AAACCBB we will get majority element as B which is infact not correct the majority element in this set is not present. A came close to being the majority element but missed by one vote. In this example A has three votes which is less than half of the votes casted.
The correctness of moore's algorithm depends on whether there is a majority element present or not. 

I am trying to propose a solution for this problem which i'll be covering in my next post.
I hope this was useful, Yawn!!!