Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

majority
element
find
how
array

How to find the majority element in an array

Educative Answers Team

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

svg viewer

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(size2)O(size^2).

Using HashMap

The basic method is computationally expensive as it has a BigO of O(size2)O(size^2). To reduce the BigO, a HashMap can be used to find the majority element in O(size)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
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring