Algorithm and Data structure

If you are here, chances are you are trying to solve the “Find majority element in an array” problem and came across the term Boyer-Moore algorithm.

Let's fast forward to the problem description :

The majority element is an element in an array that occurs more than (size/2) times in an array (where size​ is the number of elements stored in an array).

For Example, Majority element is 3 in the array {3,6,7,3,45,3,5,3,3}

Now let’s have a look at the basic approaches first.

Brute Force

Use nested loops and count the frequency of each element. If we reach an element with a frequency greater than n/2, that’s our majority element.

Complexity Analysis

Time Complexity: O(n²)

Space Complexity: O(1)

Use Sorting

Sort the array, all the similar elements will be next to each other. We can easily check the frequency of each element using the starting position and ending position of the respective element.

Complexity Analysis

Time Complexity: Sorting + Linear Traversal (Here each element is visited only once) = O(nlogn) + O(n) = O(nlogn)

Space Complexity: O(n) (In case of merge sort)

Use Hashmap

Store the count of occurrences of an element and return the element with a count greater than (size/2)

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Boyer-Moore Algorithm

We can find the majority element in linear time and constant space using this algorithm. It requires exactly 2 passes over the input list. Simple to implement, little trickier to understand.

In the first pass, we need two parameters, A candidate value(initially set to any value), and a count( store the occurrences of candidate value, set to zero initially)

For each element in the array, compare it to the current candidate value. If they are the same, we increment count by 1. If they are different, we decrement count by 1. If count becomes zero, we change the candidate with the element at the current index.

A second O(N) pass can verify that the candidate is the majority element.

How does it work

Try to think of it as a war, where a number of groups are fighting with each other. In our case(shown below), there are 4 different groups(A,B,C,D). Any soldier can kill another group’s soldier by killing himself. In the end, whatever group is left with more than half soldiers, is the winner of the war.

Try to relate it with the below diagram:

In partially pairing, the soldier of group B is killed by group C. Group A is left with more than half the soldiers, hence, the winner.

The second iteration is to verify the count of the element (found in the first iteration)

If you want to check the mathematical proof for this approach, please check the link