Boyer Moore Majority Voting Algorithm

Before you start let me set the hook for this article , this is asked in FAANG (now MAANG) companies . It runs in O(n) time and O(1) space complexity .

Why am i writing this article ?

I was doing POTD of 2nd jan on leetcode and stumbled over this algo which i had no idea about , so i thought it would be useful for others , if I tried explaining it in my own way .

When to use ?

1. When you have to match strings , in large strings .

2. Find occurences of characters .

3. Leetcode's POTD of 2nd january

How to use ?

Let's take an example of this question to understand the approach :

In this task, we must discover the number in the supplied array with a frequency more than half the array’s length, i.e. N/2 times. The length of the array is denoted by N.

Example 1 :

Input:{4,7,4,4,3,4,6,4}
Output: 4
Explanation: The length of the array is 8 and the frequency of 2 is 5 > 8/2

Example 2 :

Input:{4,7,0,5,3,4,6,4}
Output: -1
Explanation: No majority element

Now there are a few ways to solve it , obviously the brute force way , and the optimal way. Let's have a look at them one by one :

1. Brute force

2. Map approach

3. Boyer Moore's algorithm

Brute force way [ O(n^2) time ]

int findMajorityElement(vector <int> &nums) {

 int n = nums.size(), count;
 for (int i = 0; n && i <= n / 2; i++) {

 count = 1;
 for (int j = i + 1; j < n; j++)
 if (nums[j] == nums[i])
 count++;

 if (count > n / 2)
 return nums[i];
 }

 return -1;
}

We check all the elements twice , in two loops with n*n time , we check if the element is present or not , and if found that an element is greater than n/2 , then we return .

It is easy to write but not efficient enough , let's have a look at a better approach .

Map Approach [ O(n) time ]

int findMajorityElement(vector <int> &nums) {

 unordered_map <int, int> mp;

 for (auto x: nums)
 mp[x]++;

 for (auto x: mp)
 if (x.second > n / 2)
 return x.first;

 return -1;
}

We check the elements and their occurrences , and keep them in a map , with their count. Then we return the one having n/2 occurrence. In python something like Counter would be super useful .

Time complexity take : O(n)

Space complexity : O(n) , sorting frequency of each number

Boyer Moore's algorithm

The algorithm has 2 parts , the first pass identifies the majority item , the second pass just verifies that whatever first pass identified as the majority item is indeed a majority item .

Algorithm :

1. Initialize 2 variables , num and counter , both initialized to 0 .

2. Iterate over all numbers , where each number is x .

3. If count is 0 , assign num to x .

4. If current num is x , increment by one else decrement by one .

5. Reset the counter to 0 .

6. In the second pass , we just check frequency of num , and if it is greater than n/2 ,we return num else -1 .

int findMajority(vector < int > nums) {

 int n = nums.size();
 int num, count = 0;
 for (auto x: nums) {
 if (count == 0)
 num = x;

 count += (x == num ? 1 : -1);
 }

 count = 0;
 for (auto x: nums)
 if (x == num)
 count++;

 if (count > n / 2)
 return num;

 return -1;
}

Time complexity : O(n+m) or O(n)

Space complexity : O(1) , only 2 variables