The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array

Today's algorithm of the day is about finding the majority element in an array.

Given an array of size n, find the majority element. The majority element is the element that appears more than n/2 times. You may assume the array is non-empty and that there always is a majority element.

For example, if you were given the array [3,2,3], the output would be 3.

I like this problem because there are so many different ways to solve it--including iterating over the array twice, to sorting the array, to using a divide-and-conquer approach. In this post, I'm going to talk about two of the methods: creating a hash map and using the Boyer-Moore Majority Vote Algorithm.

The Hash Map Approach

Creating a hash map was the approach that I immediately thought of when I read the problem for the first time. I like hashes because they don't take up much time or space, and I find their use to be pretty intuitive.

I'll start by initializing a hash. The hash's keys are going to be each of the different numbers in the nums input array, and the values will be the number of times each of those keys are seen. (I'll be coding in JavaScript.)

function majorityElementWithHash(nums) {
  let map = {}
  //...
}

Now, I'll use a for-in loop to iterate through each number in the input array. If that number is already in the hash, then we've already seen it, which means we can just increment its value. Otherwise, we can initialize a new key-value pair, setting the value equal to 1.

function majorityElementWithHash(nums) {
  let map = {}
  for (let num of nums) {
    if (map[num]) {
      map[num]++
    } else {
      map[num] = 1
    }
  }
  //...
}

Once the loop is finished, we'll have a hash whose keys are each different number from the input array, and values are the numbers of times it was seen. We want to see which number was the majority of the input array, which means it's equal to more than half of the numbers in the input array. Another way to think about that is, if the length of the array is length, then the majority element is found at least length/2 times.

So, we can go through each key in the hash, and check if its value is greater than half of the input array's length. If it is, then that's the majority element, and we can return the element. To do this, I'll use Object.keys(hash), which returns an array of the keys of hash.

function majorityElementWithHash(nums) {
  let map = {}
  for (let num of nums) {
    if (map[num]) {
      map[num]++
    } else {
      map[num] = 1
    }
  }

  for (let elem of Object.keys(map)) {
    if (map[elem] > nums.length / 2) {
      return elem
    }
  }
}

Since the problem said that there would always be a majority element in the input array, we don't need to have an 'else' statement. So, with this first approach, we're done with the problem! This approach uses O(n) space and O(n) time.

The Boyer-Moore Majority Vote Algorithm

The Boyer-Moore Majority Vote Algorithm finds the majority element in a sequence, and uses linear time (O(n)) and constant space (O(1)). The idea behind the algorithm is to initiate a candidate and a counter. Then, walking through the elements in the sequence, if the counter is at 0, then there is no majority candidate, so the current element is the new candidate. Every time a new element is equal to the candidate, the counter increments; every time a new element is not equal to the candidate, the counter decrements. Whoever is left as the candidate at the end is the majority.

In versions of this algorithm, a second check is instituted to double check that the candidate is, in fact, found a majority of the time. However, since this problem tells us that there will always be a majority element, we don't have to do the second pass. If you want to read more about the algorithm, I recommend checking out this resource.

The code

To write out this algorithm in code, we should start with initializing a candidate and a count. We also know that we will be returning the candidate at the end, so we can include that return statement at the bottom

function majorityElementWithMoore(nums) {
  let candidate;
  let count = 0;

  //...
  return candidate;
}

Now, we will walk through each element in the nums array. For this, we can use a number of loops, but I'll be using the for-in loop.

function majorityElementWithMoore(nums) {
  let candidate;
  let count = 0;

  for (let elem of nums) {
    //...
  }

  return candidate;
}

If the count is at zero, then we can set the candidate to the current element we're on.

function majorityElementWithMoore(nums) {
  let candidate;
  let count = 0;

  for (let elem of nums) {
    if (count === 0) {
      candidate = elem;
    }
    //...
  }

  return candidate;
}

If the element we're on is equal to the candidate, then we can increment the count. If the element is different than the candidate, then we can decrement the count.

function majorityElementWithMoore(nums) {
  let candidate;
  let count = 0;

  for (let elem of nums) {
    if (count === 0) {
      candidate = elem;
    }
    if (candidate === elem) {
      count++;
    } else {
      count--;
    }
  }

  return candidate;
}

This will give us the element that is found the majority of the time in the inputted array. Because it can be a bit confusing to see why this works, I'll walk through an example.

An example

Let's say the input is [4, 5, 5, 4, 4]. We start by initializing the variable candidate, and setting count to 0.

Now, we enter for-in loop. The first element is 4. Since count === 0, the candidate is now equal to 4. Since the candidate is now equal to the element, the count increments to 1.

The next element is 5. Since the candidate does not equal the element, the count decrements to 0.

The next element is 5. Since the count is 0, the candidate now becomes the element. Since the candidate now equals the element, the count increments to 1.

The next element is 4. Since the candidate does not equal the element, the count decrements to 0.

The last element is 4. Since the count is 0, the candidate now becomes the element. Since the candidate now equals the element, the count increments.

As that's the end of the loop, we're left with the candidate 4, which is the majority element in this array.

--

Let me know in the comments section if you have any questions, or if you have other favorite ways to approach this problem.