Find majority element in an array (Boyer–Moore majority vote algorithm)

Given an array of integers containing duplicates, return the majority element in an array if present. A majority element appears more than n/2 times where n is the size of the array.

 

For example, the majority element is 2 in the array {2, 8, 7, 2, 2, 5, 2, 3, 1, 2, 2}
 

 

Naive solution would be to count frequency of each element present in the first half of the array to check if it is majority element or not. Below is the naive implementation –

 

 
The time complexity of above solution is O(n2).
 

We can improve worst case time complexity to O(nlogn) by sorting the array and then perform binary search for first and last occurrence of each element. If difference between first and last occurrence is more than n/2, we have found majority element.

 

O(n) solution –

We can use hashing to solve this problem in linear time. The idea is to store each element’s frequency in a map and return the element if its frequency becomes more than n/2. If no such element is present, then majority element does not exists in the array and we return -1. The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

C++

Download   Run Code

Output:

Majority element is 2

Java

Download   Run Code

Output:

Majority element is 2

 

Boyer–Moore majority vote algorithm –

We can find the majority element using linear time and constant space using Boyer–Moore majority vote algorithm. The algorithm can be expressed in pseudocode as the following steps:


Initialize an element m and a counter i = 0

for each element x of the input sequence:
    if i = 0, then
        assign m = x and i = 1
    else
        if m = x, then assign i = i + 1
    else
        assign i = i – 1

return m

The algorithm processes the each element of the sequence, one at a time. When processing an element x,

  1. If the counter is 0, we set the current candidate to x and we set the counter to 1.
     
  2. If the counter is not 0, we increment or decrement the counter according to whether x is the current candidate.

At the end of this process, if the sequence has a majority, it will be the element stored by the algorithm. If there is no majority element, the algorithm will not detect that fact, and will still output one of the elements. We can modify the algorithm to verify that the element found is really is a majority element or not.

C

Download   Run Code

Output:

Majority element is 2

Java

Download   Run Code

Output:

Majority element is 2


 

 
References: Boyer–Moore majority vote algorithm – Wikipedia

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
isruslan
Guest
isruslan

Here is also possible the following approach:
1. remove pairs of different elements from array
2. the element that still exists is a candidate
3. check majority of candidate, should be in len(arr) // 2 elements

gist: https://gist.github.com/isRuslan/73f79a8a50453b0c84306b1cd76ce68b

Sachin
Guest
Sachin

for array { 1,2,3,1,4,5,1,3,7,1 } result returned by boyer-moore-majority-vote-algorithm java implementation is in-correct. It’s returning 7 as result.

Anton
Guest
Anton

Hi!
Java example of Boyer-Moore algorithm provided above wouldn’t compile because compiler won’t be able to understand that m will be initialized because i is equal to 0.

Example: https://ideone.com/318q4B

Variable m should be initialized to an int value that will be rewritten if an array is non zero (it is since algorithm works for arrays with a majority elements => non empty arrays).

Anton
Guest
Anton

Ah, sorry, I was consumed by the algorithm and was actually looking at C++ code. Disregard my previous comment.

Aaditya Menon
Guest
Aaditya Menon

Array : 1 , 2 , 3 , 1
Maximum Element is 3. How come?

Ashish
Guest
Ashish

Can you please explain why we change the current candidate when count is 0 and set i=1. What is the significance of this step ?

Cliff Crosland
Guest
Cliff Crosland

Maybe another linear-time solution that uses constant extra memory? If there is a majority element, I think it would need to appear at index floor(n/2) in the sorted version of the array. Use quickselect to find that element. Then do a linear pass to verify that this element is indeed a majority.

P G
Guest

Once we will find linear time sorting algorithm.

Markus Blumenstock
Guest
Markus Blumenstock

True, if there is a majority element, the median is equal to it. Quickselect only has expected linear time, but does work in-place (if one deals with tail-recursion to eliminate the function stack).

The Blum-Floyd-Pratt-Rivest-Tarjan algorithm finds the median in O(n) deterministic time. One can rather easily modify this algorithm to work with no additional arrays, “in-place”. [One would still have the function stack of height log(n) for the recursion. But think there was a paper that deals with that, too!]