Boyer-Moore Majority Vote Algorithm
Election is going on, candidate with most votes wins.
Lets suppose, We have two candidate, Donald Trump (we will denote him using integer 2), Joe Biden (We will denote him with integer 1) and finally Kanye West with integer 0.
So the votes are stored in array, you have to start counting the votes, but wait you have to be faster than Georgia while counting. That is Time Complexity should be in order O(n). To make things more difficult, you have been strictly instructed to have Space Complexity to be O(1).
Let’s call our array arr
int arr[10]={2,2,1,1,0,0,0,0,0,0}So we can clearly see, Trump has 2 votes, Kanye West 2 and Biden has 6 votes.
Forget about constraint for a bit, We could have initialized counter for all the candidate and would have to traverse the entire and increased the counter, but that consumes space.
Hence come, Boyer-Moore Majority Vote algorithm.
Lets suppose Biden to be winner,.
But if he is the winner, he should have secured more 50 percent of vote, that means if the total vote is 10, Biden must have secure at least 6 votes to win the election.
What would be the worst case for the array for Biden to secure 5 votes out 10.
Answer where all the 1’s are away from each other.
arr={ _ , 1, _ , 1, _ , 1, _ , 1, _ , 1, _ }
Now, suppose you have to vote for Biden, where would you place that 1.
So the answer is no matter where you place, The number before or after it will always be 1.
Thats, what our algorithm is based on.
int arr[] = { 1, 2, 2, 1, 3, 1, 1, 1, 2, 1 };
I initialize a counter, which checks if the ith element== ith+1 elementIf not, the counter will be set to 0.
If true, the counter increase.We define another two variable Max store the maximum counter value and index which store its index.Let's start traversing 1, 2, 2, 1, 3, 1, 1, 11 is not equal to 2
Counter=0
Max=NULL2 is equal to 2
Counter=1.
MAX=1
Store Index position of 22 not equal to 1.
Counter=0. (Counter Decrement)
Max=1
i=11 not equal 3
Counter=0
No change in Max and Index3 not equal to 1
Counter=0
No change in Max and Index1 equal to 1
Counter=1
No change in Max and Index1 equal to 1
Counter=2
Max=2
index=6after this Counter will decrease, but what is happening here.
We print the element at index position 6 as the winner, because the variable max we declared is highest for this element 1 in our array.That's all, The implementation part is really simple.
Max will only change if the current counter is greater then max.
If you change max, we store the current index of the element.
Now, this algorithm, will return either the winner or the candidate for winner.So you have to cross check the results again, and check if the element is occurring more then N/2 times.Time Complexity here is O(2n) which is basically O(n)
