What is Boyre-Moore Voting Algorithm?

Techletter #32 | May 26, 2023

The Boyer-Moore Voting Algorithm is an efficient algorithm used to find the majority element in an array. The majority element is defined as the element that appears more than ⌊n/2⌋ times, where n is the size of the array.

Algorithm

1. Initialize two variables: count and candidate.

   • count represents the current count of the majority element (initialized as 0).

   • candidate describes the potential majority element.

2. Iterate through the array:

   • For each element in the array:

     • If count is 0, set the current element as the new candidate.

     • If the current element is equal to the candidate, increment count by 1.

     • If the current element is different from the candidate, decrement count by 1.

     • The idea is that the majority element will always have a positive count at the end, as it occurs more than ⌊n/2⌋ times.

3. After iterating through the array, the candidate will hold the potential majority element.

4. To confirm if the candidate is the majority element, perform a second pass through the array, counting the occurrences of the candidate.

   • If the count of the candidate is indeed greater than ⌊n/2⌋, return it as the majority element.

   • Otherwise, if the count is not greater than ⌊n/2⌋, then there is no majority element in the array.

Problem Statement

Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

function majorityElement(nums) {
    const n = nums.length;
    let count = 0;
    let candidate = null;
    for (let i = 0; i < n; i++) {
        if (count === 0) {
            candidate = nums[i]
        }
        count += nums[i] === majorityNumber ? 1 : -1;
    }
    return candidate;
}

The above code is a simple implementation to get the majority element in array nums***.***