Finding Majority Element in Array.

Find Majority Element in Array.


For a given input array we need to find the majority element.
An element is said to be majority element if its frequency of occurrence exceeds n/2.
Input : 3 3 4 2 4 4 2 4 4
Output: 4

Input : 3 3 4 2 4 4 2 4
Output: NONE

Solution 1: A basic solution is to scan entire array for checking for every element in the array. If any element occurs more than n/2 time, prints it and break the loop. This will be of O(n^2) complexity.

Solution 2: Sort the entire array in O(nlogn) and then in one pass keep counting the elements. This will be of O(nlogn) + O(n) = O(nlogn) complexity.

If we are sure that there is a majority element for sure that we can do it in constant time in the sorted array. I am leaving an exercise to readers that how can we do that in constant time.

Solution 3 Hash map-based approach.
We construct a hash map of the elements and store the frequency of their occurrence.


[code language=”cpp”]

#include <iostream>
using namespace std;

int main() {
int n,t,i,a;
{bool flag =false;
unordered_map<int,int> s; // a map which stores element as key and also its frequency.


auto it = s.begin();//iterator to traverse the map.
if(it->second>n/2){// comparing the value of frequency.
flag = true;

cout<<"NO Majority Element";

return 0;

Time complexity for this O(n)
However the space complexity also gets involved in this which is also O(n).

In order to reduce the space complexity refer Moore’s Voting Algorithm.

Please Login/Signup to comment