loading...
Cover image for The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array

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

alisabaj profile image Alisa Bajramovic Updated on ・5 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

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.

Initialized truth table with a count of 0, and the variables candidate and element

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.

Element is 4, candidate is 4, and count is 1

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

Element is 5, candidate is 4, count is 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.

Element is 5, candidate is 5, count is 1

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

Element is 4, candidate is 5, count is 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.

Element is 4, candidate is 4, count is 1

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.

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide