Related Tags

majority
element
find
how
array

# How to find the majority element in an array

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

## The algorithms

There are two ways to find the majority element in an array:

### Basic method

This method has two loops that count the maximum occurrence of each element in an array. Whenever the maximum count becomes greater than the size/2, the loops break and display the element as the majority element of an array. The time complexity of this method in terms of BigO is $O(size^2)$.

### Using HashMap

The basic method is computationally expensive as it has a BigO of $O(size^2)$. To reduce the BigO, a HashMap can be used to find the majority element in $O(size)$. HashMap will store the count of occurre​nces of an element and the element itself.

## Implementation

The code below uses the basic method to find the majority element of an array:

#include <iostream>
using namespace std;
//function to find the majority element
void findMajority(int arr[], int size)
{
int maxCount = 0;
int index = -1; // sentinels
for(int i = 0; i < size; i++)
{
int count = 0;
for(int j = 0; j < size; j++)
{
if(arr[i] == arr[j])
count++;
}

// update maxCount if the count of the current element is greater
if(count > maxCount)
{
maxCount = count;
index = i;
}
}

// if the maxCount is greater than size/2,
// return the corresponding element.
if (maxCount > size/2)
cout << "Majority element is " <<arr[index] << endl;

else
cout << "Majority Element does not exist" << endl;
}

// Driver code
int main()
{
int arr[] = {1,3,4,4,1,4,4};
int size = sizeof(arr) / sizeof(arr[0]);

// Calling the function
findMajority(arr, size);

return 0;
} 

## Implementation

The code below uses a HashMap to find the majority element of an array:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void findmajority(int arr[], int size)
{
unordered_map<int, int> myHashMap;
for(int i = 0; i < size; i++)
myHashMap[arr[i]]++;
int count = 0;
for(auto i : myHashMap)
{
if(i.second > size / 2)
{
count =1;
cout << "Majority elemet is " << i.first<<endl;
break;
}
}
if(count == 0)
cout << "Majority element does not exist" << endl;
}

// Driver code
int main()
{
int arr[] = {1,3,4,4,1,4,4};
int n = sizeof(arr) / sizeof(arr[0]);

// Calling the function.
findmajority(arr, n);

return 0;
} 

RELATED TAGS

majority
element
find
how
array