Boyer-Moore Voting Algorithm - The Coding Shala

Home >> Algorithms >> Boyer Moore Voting Algorithm

 In this post, we will learn what is Boyer Moore Voting Algorithm and how to implement it.

Boyer-Moore Voting Algorithm

The Boyer-Moore Majority vote algorithm is an algorithm for finding the majority of a sequence of elements using linear time and constant space. [Wikipedia]

Approach 

Initially set the first element as the Majority element and count as 1 and move the pointer forward over an element[start loop from index 1]

  • if the count is 0 then, set the current element as the Majority element and count as 1.
  • if the current element is the same as the Majority element then increase the counter by 1.
  • if the current element is not the same as the Majority element then decrease the element by 1.
When we are done, the current Majority element is our answer.

let's take an example under this.

Find Majority Element Using Boyer Moore's Voting Algorithm

In the given array we are going to find out the majority element using Boyer Moore's voting algorithm

Example
Input: nums = [2,2,1,1,1,2,2]
Output: 2

Java Program: 

class Solution {
    public int majorityElement(int[] nums) {
        int count = 1;
        int majority = nums[0];
        for(int i=1; i<nums.length; i++) {
            if(count == 0) {
                majority = nums[i];
                count = 1;
            } else if(majority == nums[i]) count++;
            else count--;
        }
        return majority;
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala