# 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++

Output:

Majority element is 2

## Java

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

Output:

Majority element is 2

## Java

Output:

Majority element is 2

(3 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest
Jørn Martin Hajek

For the O(nlogn)-solution, if you sort the array anyway, there is no need to check first and last occurrence of each element – just for the element in the middle. If there are more than n/2 occurrences of i, the middle element must be i.

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

Guest

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.

Guest

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).

Guest

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

Guest

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

Guest

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 ?

Guest
Ravi Keshari

int[] arr = { 2,8, 2,2, 7,2, 4, 1, 1 };
wrong output

Guest

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.

Guest

Once we will find linear time sorting algorithm.

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!]