Boyer Moore voting algorithm is used to find the majority element among the given sequence of elements which occurs more than N/2 times, in linear time complexity and constant space complexity.

Table of content:

1. Majority element problem
2. Brute force method + Hashmap approach
3. Approach to Boyer Moore Algorithm
4. Boyer Moore majority vote algorithm
5. Implementation
6. Time & Space complexity

Majority element problem

In this "majority element problem", we need to find the element with frequency more than or equal to 50%. This means if there are N elements, we need to find the element that occurs at least N/2 times.

Example:
Input :{1,2,2,2,2,3,5}
Output : 2
Explanation : 2 is the majority element as it occurs more than 7/2 or 3 times.

Input :{1,2,4,3,5}
Output : -1
Explanation : no majority element exists

Boyer-Moore algorithm is used to solve the majority element problem.

Brute force method + Hashmap approach

The Brute Force Method to solve the majority element problem can be using nested for loops and count each element and if count>n/2 for each element.But it is not an effiecient approach as it takes O(n^2) time.

Another approach can be to use hashmaps i.e to store the count of each element in hash map and then iterate through hash map and check if any element has count >n/2
Time Complexity for this will be O(n) and Space Complexity will be O(n).

Thus a better approach to majority element problem is to use Boyer-Moore algorithm which requires linear time and constant space.

Approach to Boyer Moore Algorithm

The algorithm in it basic sense finds a majority element, if it exists. Majority element is an element that occurs repeatedly for more than half of the input elements. However, if there is no majority, the algorithm will not detect that fact, and will still output one of the elements.

Basically the algorithm works in two part. First pass finds an element as majority element and a second pass is used to verify that the element found in the first pass is really a majority.

If the majority element does not exists, the algorithm will not detect that and thus return an arbitrary element.

So as per the above discussion we have two parts of the discussion:

1. First pass: Finds the element which could be a majority element.
2. Second pass: check the element's count which is found in the first pass is greater than n/2.

Boyer Moore majority vote algorithm

We intialise a local variable m to keep the track of a sequence element and a counter. Initially the counter is initiaised to zero. We then iterate over the elements of the sequence. While processing an element x, if the counter is zero, the algorithm stores x as its remembered sequence element and sets the counter to one. Otherwise, it compares x to the stored element. If element is same, we increment the counter and if element is not same then we decrement the counter. At the end, if the majority element exists, it will be the element stored by the algorithm.

The steps of Boyer Moore majority vote algorithm are:

1. First pass: Finding a candidate with the majority-

   • Initialize a variable m and a counter count intitialized to 0
   • For each element x of the input sequence:
   • If count is equal to zero, we assign m = x and count = 1
   • else if m is equal to x, we increment count.
   • else we decrement count.
   • Finally return the stored element m.

2. Second pass: Checking if the candidate has more than n/2 votes

   • Initialize a variable count equal to zero.
   • Loop over the sequence of elements and increment count if it is the element is same as the candidate.
   • If the count is is greater than n/2, return the candidate or else return -1.

Let us now understand this through an example.
For example we have an array of elements ={5,3,3,5,5,1,5}.

First pass:

int [] elements = {5,3,3,5,5,1,5};
i = 0, m = 5
count  = 1

int [] elements = {5,3,3,5,5,1,5};
i = 1, x=3, m = 5
count=0 (current element is not same, count = count -1)

int [] elements = {5,3,3,5,5,1,5};
i = 2, x=3, m = 3
count=1 (count was 0 so, m = x)

int [] elements = {5,3,3,5,5,1,5};
i = 3, x=5, m= 3
count=0(current element is not same, count = count-1)

int [] elements = {5,3,3,5,5,1,5};
i = 4 x=5, m= 5
count = 1(count was 0 so, m = x)

int [] elements = {5,3,3,5,5,1,5};
i = 5, x=1, m= 5,
count=0(current element is not same, count = count-1)

int [] elements = {5,3,3,5,5,1,5};
i = 6, x=5, m= 5
count = 1(count was 0 so, m = x)

Now m = 5,

Second pass:

count =0;
int i=0, x=5
count=1, (count++ as m = x)
int i=1, x=3
count=1, ( m != x)
int i=2, x=3
count=1, ( m != x)
int i=3, x=5
count=2, (count++ as m = x)
int i=4, x=5
count=3, (count++ as m = x)
int i=5, x=1
count=3, ( m != x)
int i=6, x=5
count=4, (count++ as m = x)

count=4 which is greater thsn 7/2=3.
Thus m=5 is the majority element.

Implementation

// Part of OpenGenus (iq.opengenus.org)
// Boyer Moore majority vote algorithm
#include <iostream>
using namespace std;

int findMajority(int arr[], int n)
{
	
    int m,count=0;
    for(int i=0;i<n;i++){
        if(i==0){
            m=arr[i];
            count=1;
        }
        else if (m==arr[i]){
            count++;
        }
        else{
            count--;
        }


    }

	count = 0;
	for (int i = 0; i < n; i++) {
		if (arr[i] == m) {
			count++;
		}
	}

	if (count > n / 2)
		return m;
	else
		return -1;
}
int main()
{
	int arr[] = { 1,2,2,2,2,3,5 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int majority = findMajority(arr, n);
	cout << " The majority element is : " << majority;
	return 0;
}

Time & Space complexity

Time Complexity: O(N)

Space Complexity: O(1)

So, by the end of this article at OpenGenus, you must have a better understanding of Boyer–Moore majority vote algorithm.