Boyer-Moore Majority Voting Algorithm

Boyer-Moore Majority Voting Algorithm is a popular algorithm for solving the problems where we have to find the majority elements greater than Floor(N/r), where N is the size of the array of given elements, and r is defined as the conditional variable.

It takes O(N) time complexity and O(1) space complexity for finding the results.

For example,

Q. Find the elements which occur more than N/3 (Integer Division) times in the given array.
Input: nums = [3,2,3]
Output: 3

Q. Find the elements which occur more than N/3 (Integer Division) times in the given array.
Input: nums = [1,2]
Output: [1,2]

Significance of r:

Mathematically, the maximum number of elements which occur more than (N/r) times are (r-1).

For example, the maximum number of elements which occur more than (N/2) times is 1, and maximum number of elements which occur more than (N/4) times is 3.

The r helps us in deciding the number of variables we need to initialize in the program.

Intuition behind the working of Boyer-Moore Majority Voting Algorithm?

When the elements are same as the candidate element, votes are incremented, and in case, the current element is different from the candidate element, we decrement the vote count. Since, the majority element occurs more than N/r times, the rest of the elements which are not majority elements occur less than N/r times.

We keep decreasing the count when the current element is not equal to the candidate element. If the count becomes 0, we mark the current element as candidate element, and make the count as 1.

Note: We are taking the example of N/2 condition for the working below.

Working of Boyer-Moore Majority Voting Algorithm:

Step 1: Find the candidates with majority:

• Initialize the variables say i, votes = 0, and candidate = -1
• Traverse through the array using for loop.
• If votes = 0, candidate = nums[i], make votes = 1.
• Else if the candidate = nums[i], increment votes by 1.
• Else, decrement votes by 1.

Step 2: Check if the candidate has more N/2 votes:

• Initialize a variable count = 0, and increment the count by 1 each time the candidate is same as the nums[i].
• If the count is >(N/2), return the answer as candidate.
• Else, return -1.

Codes:

---

In Java:

import java.io.*;

class Solution
{

// Function to find majority element using Boyer-Moore Majority Voting Algorithm.
    public static int findMajority(int[] nums)
    {
        int count = 0, candidate = -1;
        
        //-------Step 1--------
        
        for (int index = 0; index < nums.length; index++) {
            if (count == 0) {
                candidate = nums[index];
                count = 1;
            }
            else {
                if (nums[index] == candidate)
                    count++;
                else
                    count--;
            }
        }
        
        //-------Step 2--------
        
        count = 0;
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == candidate)
                count++;
        }
        if (count > (nums.length / 2))
            return candidate;
        return -1;
    }

    // Driver code
    public static void main(String[] args)
    {
        int arr[] = {1, 1, 1, 1, 2, 3, 4 };
        int majority = findMajority(arr);
        System.out.println(" The majority element is : "
                + majority);
    }
}

Output:

 The majority element is : 1

---

In C++:

#include <iostream>
using namespace std;
// Function to find majority element using Boyer-Moore Majority Voting Algorithm.
int findMajority(int arr[], int n)
{
    int i, candidate = -1, votes = 0;

    //------Step 1------

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

    //------Step 2------

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

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

Output:

 The majority element is : 1

---

How to handle the cases when r>2?

We can simply take more than one candidate and votes variable, according to the value of r. For example, when r = 3,

Variables can be:

candidate1 = -1;
candidate2 = -1;
votes1 = 0;
votes2 = 0;

----For Counting in Step 2----
count1 = 0;
count2 = 0;

These pairs of variables can be simultaneously checked using inside a single loop only. For larger values of r, we can use the for loop inside the main for loop, which would give the time complexity of O(N*r).

Read Next: Bellman Ford Algorithm