45

39

The majority element is the element that occurs more than half of the size of the array.

How to find the majority element in an array in `O(n)`

?

Example input:

```
{2,1,2,3,4,2,1,2,2}
```

Expected output:

```
2
```

45

39

The majority element is the element that occurs more than half of the size of the array.

How to find the majority element in an array in `O(n)`

?

Example input:

```
{2,1,2,3,4,2,1,2,2}
```

Expected output:

```
2
```

24

The majority element (if it exists) will also be the median. We can find the median in O(n) and then check that it is indeed a valid majority element in O(n). More details for implementation link

8Technically correct, but that O(N) has a very high constant factor. – marcog – 2010-12-01T20:23:41.760

1@marcog Indeed. But when the interviewer rejects the best solution, you have to get creative :) – Axn – 2010-12-01T20:38:01.310

1There are better linear time solutions. Read the duplicates in the comments above. – marcog – 2010-12-01T20:47:12.427

2@marcog The two links I saw either mentions OP's algorithm itself or a probabilistic algorithm. Neither would've been acceptable in this situation. – Axn – 2010-12-01T21:03:09.600

The problem with this solution is that it requires the additional assumption that there is a total order on the elements. Although this is satisfied in the example with integers, in general elements are not necessarily comparable. There is a solution which requires only testing for equality, not order. – Tomas Mikula – 2018-05-29T15:54:16.213

103

```
// returns -1 if there is no element that is the majority element, otherwise that element
// funda :: if there is a majority element in an array, say x, then it is okay to discard
// a part of that array that has no majority element, the remaining array will still have
// x as the majority element
// worst case complexity : O(n)
int findMajorityElement(int* arr, int size) {
int count = 0, i, majorityElement;
for (i = 0; i < size; i++) {
if (count == 0)
majorityElement = arr[i];
if (arr[i] == majorityElement)
count++;
else
count--;
}
count = 0;
for (i = 0; i < size; i++)
if (arr[i] == majorityElement)
count++;
if (count > size/2)
return majorityElement;
return -1;
}
```

6This is clearly the best solution. It is a special case of a stream counting algorithm, where only one element is tracked. (You can use a collection of `n`

"majority elements" to find any element that constitutes 1 / (n + 1) or more of the elements. For example, with 9 majority elements, you find any element that occurs at least 10% of the time. – erickson – 2012-04-14T15:19:40.537

2Great solution, much better than the accepted answer ! – cyclotrojan – 2012-10-21T09:53:40.303

4for an input array with {2,1,2,4,1,2}, shouldn't this method return 2. but it is returning -1. – brain storm – 2014-02-21T23:57:17.457

3@brainstorm: In an array of size 6, the majority element must appear at least 4 times. In your array, "2" only appears 3 times. – Michael Liu – 2014-03-13T18:40:56.347

12This is Moore’s Voting Algorithm, should be attributed properly. – Atiq Rahman – 2015-10-17T05:11:04.880

1what if the majority is -1? – Roy Guanyu – 2016-11-06T16:05:23.187

27

It is sad to see that in 5 years no one has written a proper explanation for this problem.

This is a standard problem in streaming algorithms (where you have a huge (potentially infinite) stream of data) and you have to calculate some statistics from this stream, passing through this stream once.

Clearly you can approach it with hashing or sorting, but with a potentially infinite stream you can clearly run out of memory. So you have to do something smart here.

**The majority element is the element that occurs more than half of the size of the array**. This means that the majority element occurs more than all the other elements combined. That is, if you count the number of times the majority element appears, and subtract the number of occurrences of all the other elements, you will get a positive number.

So if you count the occurrences of some element, and subtract the number of occurrences of all other elements and get the number 0 - then your original element can't be a majority element. This is the basis for a correct algorithm:

*Declare two variables, counter and possible_element. Iterate the stream, if the counter is 0 - your overwrite the possible element and initialize the counter, if the number is the same as possible element - increase the counter, otherwise decrease it.* Python code:

```
def majority_element(arr):
counter, possible_element = 0, None
for i in arr:
if counter == 0:
possible_element, counter = i, 1
elif i == possible_element:
counter += 1
else:
counter -= 1
return possible_element
```

It is clear to see that the algorithm is `O(n)`

with a very small constant before `O(n)`

(like 3). Also it looks like the space complexity is `O(1)`

, because we have only three variable initialized. The problem is that one of these variables is a counter which potentially can grow up to `n`

(when the array consists of the same numbers). And to store the number `n`

you need `O(log (n))`

space. So **from theoretical point of view** it is `O(n)`

time and `O(log(n))`

space. **From practical**, you can fit 2^128 number in a longint and this number of elements in the array is unimaginably huge.

Also note that the algorithm works only if there is a majority element. If such element does not exist it will still return some number, which will surely be wrong. (it is easy to modify the algorithm to tell whether the majority element exists)

History channel: this algorithm was invented somewhere in 1982 by Boyer, Moore and called Boyer–Moore majority vote algorithm

15

**Majority Element:**

A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).

**Finding a Candidate:**

The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.

```
findCandidate(a[], size)
1. Initialize index and count of majority element
maj_index = 0, count = 1
2. Loop for i = 1 to size – 1
(a)If a[maj_index] == a[i]
count++
(b)Else
count--;
(c)If count == 0
maj_index = i;
count = 1
3. Return a[maj_index]
```

Above algorithm loops through each element and maintains a count of a[maj_index], If next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then changes the maj_index to the current element and sets count to 1. First Phase algorithm gives us a candidate element. In second phase we need to check if the candidate is really a majority element.

**Second phase** is simple and can be easily done in O(n). We just need to check if count of the candidate element is greater than n/2.

Read geeksforgeeks for more details

3

Time:O(n)

Space:O(n)

Walk the tree and count the occurrence of elements in a hash table.

Time:O(n lg n) or O(n*m)(depends on the sort used)

space:(1)

sort the array then count occurrences of the elements.

The interview correct answer: Moore’s Voting Algorithm

Time: O(n)

Space:O(1)

Walk the list compare the current number vs current best guess number. If the number is equal to the current best guess number increment a counter, otherwise decrement the counter and if the counter hits zero replace the current best guess number with the current number and set the counter to 1. When you get to the end the current best guess is the Candidate number, walk the list again just counting instances of the candidate. If the final count is greater than n/2 then it is the majority number otherwise there isn't one.

2

*In Monte-Carlo algorithm,*

```
Majority (a,n)
//a[]-array of 'n' natural numbers
{
j=random(0,1,....,n-1)
/*Selecting the integers at random ranging from 0 to n-1*/
b=a[j];c=0;
for k from 0 to n-1 do
{
if a[k]=b then,
c=c+1;
}
return (c>n/2)
}
```

2

How about a random sampling approach? You could sample, say sqrt(n) elements and for each element that occurred more than sqrt(n) / 4 times (can be accomplished naively in O(n) time and O(sqrt(n)) space), you could check whether it was a majority element in O(n) time.

This method finds the majority with high probability because the majority element would be sampled at least sqrt(n) / 2 times in expectation, with a standard deviation of at most n^{1/4} / 2.

Another sampling approach that is similar to an approach I saw in one of the duplicate links is to draw two samples, and if they are equal verify that you have found the majority element in O(n) time. The additional verification step is necessary because the other elements besides the majority may not be distinct.

Consider a case where you've got 1000000 As and 1000001 Bs - the first approach takes 1000 samples and still makes a close to 50/50 guess. The second idea's just groping at an answer (take 2, why not 3, or 4?) - average-case behaviour's not bad, but pathologically-worst-case behaviour is terrible. Still, I appreciate the answer Ali linked is a high bar to measure up to, and I'm not saying I've any better ideas. – Tony Delroy – 2010-12-03T05:01:14.700

@Tony, The first approach would not make a guess, it would try both A and B, assuming there were at least 250 samples of each. In what respect is the second answer just groping at an answer? It runs in expected linear time (as opposed to linear time with high probability, like the first one), and keeps the code very simple. – jonderry – 2010-12-03T05:39:01.727

you're right... I didn't pay attention to your "top four" provision, sorry... does make it overwhelmingly likely to succeed. 2nd one... maybe it's not what you're intending, but my reading of the algorithm is to pick one number from anywhere in the data set, then pick another, and if they correspond do a full verification (otherwise start over). When two elements are nearly balanced, there's still only about 50% chance of it picking the majority element on any given run. – Tony Delroy – 2010-12-03T07:31:07.660

1

To find the majority of an element in an array then you can use Moore's Majority Vote Algorithm which is one of best algorithm for it.

**Time Complexity:** `O(n) or linear time`

**Space Complexity:** `O(1) or constant space`

Read more at Moore's Majority Vote Algorithm and GeeksforGeeks

0

```
int majorityElement(int[] num) {
int major=num[0], count = 1;
for(int i=1; i<num.length;i++){
if(count==0){
count++;
major=num[i];
}
else if(major==num[i]){
count++;
}
else
count--;
}
return major;
}
```

**Time Complexity O(n)**

0

```
public class MajorityElement
{
public static void main(String[] args)
{
int arr[]={3,4,3,5,3,90,3,3};
for(int i=0;i<arr.length;i++)
{
int count=0;
int j=0;
while(j<arr.length-1)
{
if(i==j)
j=j+1;
if(arr[i]==arr[j])
count++;
j++;
}
if(count>=arr.length/2)
{
System.out.println("majority element"+arr[i]);
break;
}
}
}
```

}

0

A modified version Boyer's Algorithm,

- 3 passes where,
- In the first pass, we do a forward iteration of the array
- In the second pass, we do a reverse iteration of the array.
- In third pass, get counts for both the majority elements obtained in first and second passes.

Technically a linear complexity algorithm (O(3n)). I believe this should work for an array with a majority element that occurs at least n/2 times.

```
#include <iostream>
#include <vector>
template <typename DataType>
DataType FindMajorityElement(std::vector<DataType> arr) {
// Modified BOYERS ALGORITHM with forward and reverse passes
// Count will stay positive if there is a majority element
auto GetMajority = [](auto seq_begin, auto seq_end) -> DataType{
int count = 1;
DataType majority = *(seq_begin);
for (auto itr = seq_begin+1; itr != seq_end; ++itr) {
count += (*itr == majority) ? 1 : -1;
if (count <= 0) { // Flip the majority and set the count to zero whenever it falls below zero
majority = *(itr);
count = 0;
}
}
return majority;
};
DataType majority1 = GetMajority(arr.begin(), arr.end());
DataType majority2 = GetMajority(arr.rbegin(), arr.rend());
int maj1_count = 0, maj2_count = 0;
// Check if any of the the majority elements is really the majority
for (const auto& itr: arr) {
maj1_count += majority1 == itr ? 1 : 0;
maj2_count += majority2 == itr ? 1 : 0;
}
if (maj1_count >= arr.size()/2)
return majority1;
if (maj2_count >= arr.size()/2)
return majority2;
// else return -1
return -1;
}
```

0

Thanks for the previous answers which inspired me to know Bob Boyer's algo. :)

Java generic version: A modified version of Boyer's Algorithm

Note: array of primitive type could use wrapper.

```
import com.sun.deploy.util.ArrayUtil;
import com.sun.tools.javac.util.ArrayUtils;
/**
* Created by yesimroy on 11/6/16.
*/
public class FindTheMajority {
/**
*
* @param array
* @return the value of the majority elements
*/
public static <E> E findTheMajority(E[] array){
E majority =null;
int count =0;
for(int i=0; i<array.length; i++){
if(count==0){
majority = array[i];
}
if(array[i].equals(majority)){
count++;
}else{
count--;
}
}
count = 0;
for(int i=0; i<array.length ; i++){
if(array[i].equals(majority)){
count++;
}
}
if(count > (array.length /2)){
return majority;
}else{
return null;
}
}
public static void main(String[] args){
String[] test_case1 = {"Roy","Roy","Roy","Ane","Dan","Dan","Ane","Ane","Ane","Ane","Ane"};
Integer[] test_case2 = {1,3,2,3,3,3,3,4,5};
System.out.println("test_case1_result:" + findTheMajority(test_case1));
System.out.println("test case1 the number of majority element should greater than" + test_case1.length/2);
System.out.println();
System.out.println("test_case2_result:" + findTheMajority(test_case2));
System.out.println("test case2 the number of majority element should greater than" + test_case2.length/2);
System.out.println();
}
```

}

0

//Suppose we are given an array A. //If we have all the elements in the given array such each element is less than K, then we can create an additional array B with length K+1.

//Initialize the value at each index of the array with 0. //Then iterate through the given array A, for each array value A[i], increment the value with 1 at the corresponding index A[i] in the created array B.

//After iterating through the array A, now iterate through the array B and find the maximum value. If you find the value greater than the n/2 then return that particular index.

//Time Complexity will be O(n+K) if K<=n then equivalent to O(n).

//We have a constraint here that all elements of the array are O(K). //Assuming that each element is less than or equal to 100, in this case K is 100.

```
import javax.print.attribute.standard.Finishings;
public class MajorityElement {
private static int maxElement=100;
//Will have all zero values initially
private static int arrB[]=new int[maxElement+1];
static int findMajorityElement(int[] arrA) {
int count = 0, i, majorityElement;
int n=arrA.length;
for (i = 0; i < n; i++) {
arrB[arrA[i]]+=1;
}
int maxElementIndex=1;
for (i = 2; i < arrB.length; i++){
if (arrB[i]>n/2) {
maxElementIndex=i;
break;
}
}
return maxElementIndex;
}`
public static void main(String[] args) {
int arr[]={2,6,3,2,2,3,2,2};
System.out.println(findMajorityElement(arr));
}
}
```

0

If you are allowed to create a hash-table and assume hash-entry lookup is constant you just hash_map each entry against the number of occurrences.

You could do a second pass through the table you get the one with the highest count, but if you know in advance the number of elements in the table, you will know immediately if we have a majority element on the first pass when we hit the required count on the element.

You cannot guarantee of course that there is even a sequence of 2 consecutive occurrences of the element eg 1010101010101010101 has no consecutive 1s but it is a majority element.

We are not told anything about whether there is any kind of ordering on the element type although obviously we must be able to compare two for equality.

0

This will Help you and if two elements repeat same number of times if will show none.

```
int findCandidate(int a[], int size)
{
int count,temp=0,i,j, maj;
for (i = 0; i < size; i++) {
count=0;
for(j=i;j<size;j++)
{
if(a[j]==a[i])
count++;
}
if(count>temp)
{
temp=count;
maj=i;
}
else if(count==temp)
{
maj=-1;
}
}
return maj;
}
```

0

This is how I do it in C++ using vector and multimap (JSON with repeat keys).

```
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <iterator>
using namespace std;
vector <int> majorityTwoElement(vector <int> nums) {
// declare variables
multimap <int, int> nums_map;
vector <int> ret_vec, nums_unique (nums);
int count = 0;
bool debug = false;
try {
// get vector of unique numbers and sort them
sort(nums_unique.begin(), nums_unique.end());
nums_unique.erase(unique(nums_unique.begin(), nums_unique.end()), nums_unique.end());
// create map of numbers and their count
for(size_t i = 0; i < nums_unique.size(); i++){
// get number
int num = nums_unique.at(i);
if (debug) {
cout << "num = " << num << endl;
}
// get count of number
count = 0; // reset count
for(size_t j = 0; j < nums.size(); j++) {
if (num == nums.at(j)) {
count++;
}
}
// insert number and their count into map (sorted in ascending order by default)
if (debug) {
cout << "num = " << num << "; count = " << count << endl;
}
nums_map.insert(pair<int, int> (count, num));
}
// print map
if (debug) {
for (const auto &p : nums_map) {
cout << "nums_map[" << p.first << "] = " << p.second << endl;
}
}
// create return vector
if (!nums_map.empty()) {
// get data
auto it = prev(nums_map.end(), 1);
auto it1 = prev(nums_map.end(), 2);
int last_key = it->first;
int second_last_key = it1->first;
// handle data
if (last_key == second_last_key) { // tie for repeat count
ret_vec.push_back(it->second);
ret_vec.push_back(it1->second);
} else { // no tie
ret_vec.push_back(it->second);
}
}
} catch(const std::exception& e) {
cerr << "e.what() = " << e.what() << endl;
throw -1;
}
return ret_vec;
}
int main() {
vector <int> nums = {2, 1, 2, 3, 4, 2, 1, 2, 2};
try {
// get vector
vector <int> result = majorityTwoElement(nums);
// print vector
for(size_t i = 0; i < result.size(); i++) {
cout << "result.at(" << i << ") = " << result.at(i) << endl;
}
} catch(int error) {
cerr << "error = " << error << endl;
return -1;
}
return 0;
}
// g++ test.cpp
// ./a.out
```

-4

Sort the given array : O(nlogn).

If the array size is 7, then the majority element occurs atleast ceiling(7/2) = 4 times in the array.

After the array is sorted, it means that if the majority element is first found at position i, it is also found at position i + floor(7/2) (4 occurences).

Example - Given array A - {7,3,2,3,3,6,3}

Sort the array - {2,3,3,3,3,6,7}

The element 3 is found at position 1 (array index starting from 0.) If the position 1 + 3 = 4th element is also 3, then it means 3 is the majority element.

if we loop through the array from beginning..

compare position 0 with position 3, different elements 2 and 3. compare position 1 with position 4, same element. We found our majority match!

Complexity - O(n)

Total time complexity - O(n).

3If the first step is O(nlogn), how is the total time complexity O(n)?? By the way, if you do have a sorted array then all you need to do is check if the middle element is a majority element. – interjay – 2013-11-12T09:35:58.600

Possible duplicate http://stackoverflow.com/questions/1191740/find-a-number-where-it-appears-exactly-n-2-times although that question gaurantees the number occurs exactly N/2 times, this one says more than N/2.

– marcog – 2010-12-01T14:18:34.990For a proper explanation of this classical problem see my answer

– Salvador Dali – 2016-03-26T17:56:38.173