Luke Fisher

Recently I’ve been trying to get prepared for interviews which means learning a lot of new algorithms. The Boyer-Moore voting algorithm finds the majority element of a list of items in linear time and constant space. The algorithm itself is quite simple and easy to grasp, but thinking of it on your own during an interview would require a lot of creativity. ¹

The Basic Idea

The algorithm contains two local variables: candidate and count. The list of numbers passed in as a parameter we’ll call nums.

candidate is initialized to the first element of the list and count is initialized to 1.

Next we loop over nums[1:len(nums) - 1] (Essentially, all numbers except the first since that’s what the initialized values capture) and check if nums[i] is equal to our current candidate. Two things can happen:

If the value at nums[i] is equal to candidate, then we can increment the count variable.
If the value at nums[i] is not equal to candidate, then we decrement the count variable. Additionally, if the count variable becomes negative, candidate is set to nums[i]

After iterating through each number in the list, we return the value, candidate, as our majority element.

Note: The traditional algorithm assumes the existence of a majority element. Say for example you had a list with three distinct numbers each appearing twice. There is no majority element in this case. Practical applications of this may require another loop to confirm that the returned candidate actually appears more than len(nums) // 2 times.

A Simple Implementation

l = [1,1,1,2,2,2]

def find_mode(l: list) -> int:
    if len(l) < 1: # Length has to be greater than 0.
        return None

    candidate = l[0] # Initialize candidate to the first element.
    count = 1 # Initialize the count to 1.

    for i in range(1, len(l)): # Loop through all elements except the first.
        if l[i] == candidate:
            count += 1 # Increment count if another instance of candidate is found.
        else:
            count -= 1 # Otherwise decrement the count.

            if count < 0: # Properly update the candidate once the count becomes -1.
                candidate = l[i]

    if l.count(candidate) > len(l) // 2: # Confirm that the candidate is actually the majority element.
        return candidate

    return None # Return None if the candidate isn't the true majority element.

print(find_mode(l))

Wrapping Up

In conclusion, the Boyer-Moore voting algorithm is the most efficient way to find the majority element in a list of items. Other approaches either include using extra space in the form of a hashmap or extra time by doing sorting. The brute force solution runs in quadratic time with no extra space. Here’s a few practice problems to utilize the idea behind this algorithm.

The application of this algorithm is a little niche, but it’s still a great example of an online algorithm and a streaming algorithm.

For me, the simplicity of an algorithm can often be a point of frustration. I say to myself, “Why didn’t I think of that?”. In reality, most people’s first intuition rarely produces the most efficient and elegant solution. ↩︎

LUKE FISHER

The Boyer-Moore Voting Algorithm

The Basic Idea

A Simple Implementation

Wrapping Up