What is Boyer-Moore majority vote algorithm?

Boyer–Moore majority vote algorithm

The Boyer-Moore voting algorithm is a clever method to find the majority element in an array (an element that appears more than n/2 times) using O(1) space and O(n) time. Here’s how it works:

First, let’s use an analogy: Imagine you’re watching a battle between different teams. Every time you see members of different teams, they eliminate each other (like in a duel). The last team standing is likely to be the majority.

Here’s how the algorithm implements this idea:

def find_majority(nums):
    candidate = None
    count = 0
    
    # First pass: find a candidate
    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1
    
    return candidate

Let’s break down how it works:

1. We start with a candidate (initially None) and a count (initially 0)
2. When we see a new element:
   • If our count is 0, we pick this element as our new candidate
   • If this element matches our candidate, we increment the count
   • If this element is different from our candidate, we decrement the count

Think of the count as keeping track of the “net votes” for our current candidate. When the count reaches zero, it means our current candidate has been “eliminated” by equal opposition.

Here’s a concrete example:

array = [2, 2, 1, 1, 2, 2, 1, 2, 2]
 
Step-by-step:
2 → candidate = 2, count = 1
2 → candidate = 2, count = 2
1 → candidate = 2, count = 1
1 → candidate = 2, count = 0
2 → candidate = 2, count = 1
2 → candidate = 2, count = 2
1 → candidate = 2, count = 1
2 → candidate = 2, count = 2
2 → candidate = 2, count = 3

The beauty of this algorithm is that if there is a majority element, it must be our final candidate. Why? Because the majority element appears more times than all other elements combined, so it can’t be completely “eliminated” by the other elements.

Note: If you need to verify that the candidate is actually a majority element, you’ll need a second pass through the array to count its occurrences. The algorithm as shown just finds a candidate that could be the majority element.

This algorithm is particularly elegant because it solves what seems like a complex problem with just a few lines of code and constant extra space. Source