Boyer-Moore Majority Voting Algorithm

The Boyer-Moore Majority Voting Algorithm is a technique used to find the majority element in a given array or sequence of elements in linear time using constant space. The majority element is the element that appears more than half of the time in the array.

For example, let’s consider the following array:

[1, 2, 3, 2, 2, 2, 4, 2, 2]

In this array containing 9 elements, the element 2 appears 6 times, which is more than half the length of the array. Therefore, 2 is the majority element in this example.

On the other hand, consider the following array:

[1, 2, 3, 4, 5]

In this array, there is no element that appears more than half the time. Each element appears only once, so there is no majority element.

Algorithm

The Boyer-Moore Majority Voting Algorithm works by keeping track of a potential majority element and a count. If the current element is the same as the potential majority element, the count is incremented. If the current element is different from the potential majority element, the count is decremented. If the count reaches 0, the potential majority element is updated to the current element. At the end of the algorithm, we check the count of potential majority element and if it is more than half the total number of elements, we have the majority element. Otherwise it means there is no element which is repeated more than half the number of elements in the array. Below is the implementation:


def find_majority(arr):
  # Initialize majority_candidate to None and count to 0
  majority_candidate = None
  count = 0

  # Iterate through the array
  for candidate in arr:
    # If count is 0, set majority_candidate to the current element
    if count == 0:
      majority_candidate = candidate

    # If the current element is the same as the majority_candidate, increment count
    # Otherwise, decrement count
    if candidate == majority_candidate:
      count += 1
    else:
      count -= 1
  
  # Initialize majority_count to 0
  majority_count = 0

  # Iterate through the array again 
  # to count the occurrences of the majority_candidate
  for candidate in arr:
    if candidate == majority_candidate:
      majority_count += 1
  
  # If the majority_count is greater than half the length of the array,
  # print the majority element and return it
  if majority_count > len(arr) / 2:
    print(f"Majority element for {arr} is {majority_candidate}")
    return majority_candidate

  # If there's no majority element, print a message and return None
  print(f"There's no Majority element for {arr}")
  return None

# Let's test the majority element finding algorithm
find_majority([1, 2, 3, 2, 2, 2, 4, 2, 2])
find_majority([1, 2, 3, 4, 5])


#include <iostream>
#include <vector>

// Function to find the majority element in the given array
int findMajority(std::vector<int>& arr) {
  // Initialize majority_candidate to -1 and count to 0
  int majorityCandiate = -1;
  int count = 0;

  // Iterate through the array
  for (int candidate : arr) {
    // If count is 0, set majorityCandiate to the current element
    if (count == 0) {
      majorityCandiate = candidate;
    }

    // If the current element is the same as the majorityCandiate, increment count
    // Otherwise, decrement count
    if (candidate == majorityCandiate) {
      count++;
    } else {
      count--;
    }
  }

  // Initialize majorityCount to 0
  int majorityCount = 0;

  // Iterate through the array again 
  // to count the occurrences of the majorityCandiate
  for (int candidate : arr) {
    if (candidate == majorityCandiate) {
      majorityCount++;
    }
  }

  // If the majorityCount is greater than half the length of the array,
  // print the majority element and return it
  if (majorityCount > arr.size() / 2) {
    std::cout << "Majority element for [";
    for (int i = 0; i < arr.size(); i++) {
      std::cout << arr[i] << (i == arr.size() - 1 ? "" : ", ");
    }
    std::cout << "] is " << majorityCandiate << std::endl;
    return majorityCandiate;
  }

  // If there's no majority element, print a message and return -1
  std::cout << "There's no Majority element for [";
  for (int i = 0; i < arr.size(); i++) {
    std::cout << arr[i] << (i == arr.size() - 1 ? "" : ", ");
  }
  std::cout << "]" << std::endl;
  return -1;
}

int main() {
  // Let's test the majority element finding algorithm
  std::vector<int> arr1 = {1, 2, 3, 2, 2, 2, 4, 2, 2};
  findMajority(arr1);

  std::vector<int> arr2 = {1, 2, 3, 4, 5};
  findMajority(arr2);

  return 0;
}


/**
 * Finds the majority element in the given array.
 * @param {number[]} arr - The input array.
 * @returns {number|null} - The majority element, or null if there is no majority element.
 */
function findMajority(arr) {
  // Initialize majority_candidate to null and count to 0
  let majorityCandiate = null;
  let count = 0;

  // Iterate through the array
  for (const candidate of arr) {
    // If count is 0, set majorityCandiate to the current element
    if (count === 0) {
      majorityCandiate = candidate;
    }

    // If the current element is the same as the majorityCandiate, increment count
    // Otherwise, decrement count
    if (candidate === majorityCandiate) {
      count++;
    } else {
      count--;
    }
  }

  // Initialize majorityCount to 0
  let majorityCount = 0;

  // Iterate through the array again to count the occurrences of the majorityCandiate
  for (const candidate of arr) {
    if (candidate === majorityCandiate) {
      majorityCount++;
    }
  }

  // If the majorityCount is greater than half the length of the array,
  // print the majority element and return it
  if (majorityCount > arr.length / 2) {
    console.log(`Majority element for ${arr} is ${majorityCandiate}`);
    return majorityCandiate;
  }

  // If there's no majority element, print a message and return null
  console.log(`There's no Majority element for ${arr}`);
  return null;
}

// Let's test the majority element finding algorithm
findMajority([1, 2, 3, 2, 2, 2, 4, 2, 2]);
findMajority([1, 2, 3, 4, 5]);


import java.util.Arrays;

public class Main {
  // Function to find the majority element in the given array
  public static Integer findMajority(int[] arr) {
    // Initialize majority_candidate to null and count to 0
    Integer majorityCandiate = null;
    int count = 0;

    // Iterate through the array
    for (int candidate : arr) {
      // If count is 0, set majority_candidate to the current element
      if (count == 0) {
        majorityCandiate = candidate;
      }

      // If the current element is the same as the majority_candidate, increment count
      // Otherwise, decrement count
      if (candidate == majorityCandiate) {
        count++;
      } else {
        count--;
      }
    }

    // Initialize majority_count to 0
    int majorityCount = 0;

    // Iterate through the array again 
    // to count the occurrences of the majority_candidate
    for (int candidate : arr) {
      if (candidate == majorityCandiate) {
        majorityCount++;
      }
    }

    // If the majority_count is greater than half the length of the array,
    // print the majority element and return it
    if (majorityCount > arr.length / 2) {
      System.out.printf("Majority element for %s is %d%n", Arrays.toString(arr), majorityCandiate);
      return majorityCandiate;
    }

    // If there's no majority element, print a message and return null
    System.out.printf("There's no Majority element for %s%n", Arrays.toString(arr));
    return null;
  }

  public static void main(String[] args) {
    // Test the majority element finding algorithm
    findMajority(new int[] {1, 2, 3, 2, 2, 2, 4, 2, 2});
    findMajority(new int[] {1, 2, 3, 4, 5});
  }
}

Sample Output:

Majority element for [1, 2, 3, 2, 2, 2, 4, 2, 2] is 2
There's no Majority element for [1, 2, 3, 4, 5]

Here’s how the code works:

The find_majority function takes an array arr as input.
It initializes two variables: majority_candidate and count. majority_candidate is set to None, and count is set to 0.
The function then iterates through the array arr. For each element in the array:
- If count is 0, it sets majority_candidate to the current element.
- If the current element is the same as majority_candidate, it increments count.
- If the current element is different from majority_candidate, it decrements count.
After the first iteration, majority_candidate will hold the potential majority element.
The function then iterates through the array again to count the occurrences of majority_candidate.
If the count of majority_candidate is greater than half the length of the array, the function prints the majority element and returns it.
If there is no majority element (i.e., the count of majority_candidate is not greater than half the length of the array), the function prints a message and returns None.

Time and Space Complexity

The time complexity of this algorithm is O(n), where n is the length of the input array, as it only requires two passes through the entire array: First pass to find out potential majority element and a second pass to confirm if it’s a majority element. The space complexity is O(1), as it only uses a constant amount of extra space.

Intuition behind the Algorithm

Imagine that there are 2n+1 people and every one has a vote. Let’s assume that there is a winner among them who gets more than n votes. The worst that can happen is all the people who did not vote for the winner can get together and vote for a single opponent. In other words, in this scenario, there are n candidates who vote for a single person and m+1 candidates who vote for the majority candidate.

Let’s say the majority element is m and all other elements are o. In this case the worst order of combination will be o, m, o, m, o, m, o, m, m.

If you dry run the algorithm for the above combination, the value of majority element will be o until the last but one element and the count will be zero. With the last element, the majority element is reset again as count is zero and so the final value of majority element will be m.

Explanation borrowed from this post

It might be difficult to understand this but it’ll get easier if you try to create different arrangements and dry run the algorithm.