Boyer-Moore Majority Voting Algorithm
The Boyer-Moore Majority Voting Algorithm finds the majority element among the given elements with more than N/2 occurrences.
But why do we need an algorithm for that, isn’t counting and then comparing the numbers insufficient to find the majority element?
Let’s understand this using an example,
Let’s say you’ve got a bag full of colorful balls in three colors: Red, Blue, and Green. Your task? Figure out which is the majority color in the bag.
Simple, right?
You start counting each color, one ball at a time. And you do this for all the balls in the bag and at the end, you have a count of exactly how many balls you have for each color.
By comparing the counts, we determine which ball’s count is more than N/2, where N is the total number of balls in the bag. In our example, the Red color is in the majority. (5 red balls > 8/2)
Problem?
This method works fine, however, it requires extra space. For instance, if we have M different types of balls, we’d need to track the counts of M distinct balls in the bag.
We can do this either by using a hashmap with M entries or creating an additional array to store the counts of M different balls using their indices. But this would end up taking O(M) Space Complexity, which is inefficient if M ends up being a very large number or if we have a memory-constrained environment and dealing with extremely large datasets.
This is where Boyer and Moore’s Voting Algorithm comes in, where it eliminates the need for storing counts, making it efficient for finding the majority element in constant space. The algorithm works based on these observations:
- If we cancel out each occurrence of an element with all other elements different from it, the majority element, if it exists, will still remain.
- After these cancellations, if the majority element exists, it will still be the majority element.
Pseudo Algorithm
- Start by assuming that the first element of the array is the majority element.
- Set a counter variable to keep track of the frequency of the majority element.
- Iterate through the array starting from the second element.
- If the current element of the array is the same as the majority element, increment the counter variable.
- If the current element is not the same as the majority element, decrement the counter variable. This is done to nullify one vote of the majority element.
- If the counter reaches 0, update the majority element to the current element and reset the counter to 1.
- After traversing the array, count the occurrences of the majority element.
- If the count of the majority element is greater than half the size of the array, it is the majority element. Print the element.
- If the count is not greater than half the size of the array, there is no majority element.
Let’s understand this with a dry run on our previous example,
- Initialization, Count = 0, No Majority Element selected yet.
- First ball (Red), Majority Element = Red, Count = 1.
- Second ball (Red), Majority Element = Red, Count (Increases by 1) = 2.
- Third ball (Blue), Majority Element = Red, Count (Decreases by 1) = 1.
Note: Since the Count is not zero yet, the Majority Element will remain the same.
- Fourth ball (Red), Majority Element = Red, Count (Increases by 1) = 2.
- Fifth ball (Red), Majority Element = Red, Count (Increases by 1) = 3.
- Sixth ball (Green), Majority Element = Red, Count (Decreases by 1) = 2.
Note: Since the Count is not zero yet, the Majority Element will remain the same.
- Seventh ball (Blue), Majority Element = Red, Count (Decreases by 1) = 1.
Note: Since the Count is not zero yet, the Majority Element will remain the same.
- Eighth ball (Red), Majority Element = Red, Count (Increases by 1) = 2.
- After all these steps, the value of the Count variable is 2, and the candidate for the Majority Element is Red.
- If we count the number of total red balls in the bag then it will sum up to 5 which is greater than N/2 i.e. 8/2 (N is the total number of balls in the bag).
- So we can conclude that Red color balls are in the majority.
Let’s see the implementation of this algorithm.
JavaScript Code
Time Complexity: O(N)
In the above code, we traverse the array twice, first to find the potential candidate and second time to count the occurrence of the candidate in the array. Both these traversals take linear time.
Space Complexity: O(1)
Since no extra space is used to store the count of the elements of the input array, the space complexity is constant.
I hope this article has provided you with valuable insights and helped you understand Boyer and Moore’s voting Algorithm. Feel free to ask questions in the comment section. Happy coding!