### 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