Majority Element

Find the majority element in the given array of size n. 

A majority element in an array is an element that appears more than n/2 times in the array

Input : {3, 3, 4, 2, 4, 4, 2, 4, 4}
Output : 4
Explanation: The frequency of 4 is 5 which is greater
than the half of the size of the array size. 

Input : {1,2,3}
Output : -1
Explanation: There is no element whose frequency is
greater than the half of the size of the array size.  

METHOD 1  (easy two loops method)

• Algorithm: 
1. Create a variable to store the max count, count = 0
2. Traverse through the array from start to end.
3. For every element in the array run another loop to find the count of same elements in the given array.
4. If the count is greater than the max count update the max count and store the index in another varaible.
5. If the maximum count is greater than the half the size of the array, print the element. Else print -1.

implementation:

void findMajority(int arr[], int n)
{
    int maxCount = 0;
    int index = -1; 
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (arr[i] == arr[j])
                count++;
        }
 
        // update maxCount if count of
        // current element is greater
        if (count > maxCount) {
            maxCount = count;
            index = i;
        }
    }
 
    // if maxCount is greater than n/2
    // return the corresponding element
    if (maxCount > n / 2)
        cout << arr[index] << endl;
 
    else
        cout <<-1<< endl;
}

• Time Complexity: O(n*n). 
  both the loops traverse the array from start to end, so the time complexity is O(n^2).
• Auxiliary Space : O(1). 
  
  

  

METHOD 2  (sorting)

when array is sorted only middle element has the chances of being a majority element

so we will check if middle element count is greater than the half the size of the array, print the middle element. Else print -1.

Algorithm: 

1. sort the array
2. find the middle element 
3. count the number of occurance of middle element by traversing from start to the end of the array
4. if count is greater than the half the size of the array, print the element. Else print -1.

implementation:

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

void findMajority(int arr[], int n)
{
   sort(arr,arr+n);  //sort the array
   
   int count =0;   
   
   int mid=(n-1)/2;   // find the middle element
   
   //check the count of mid element
   for(int i=0;i<n;i++)
   {
       if(arr[mid]==arr[i])
       count++;
   }
   
   //check if the count of mid element is greater than n/2
   if(count>n/2)
   cout<<arr[mid]<<endl;
   else
   cout<<-1<<endl;
   
   
}
 
int main() 
{ 
    int n;
    cin>>n;
    int a[n];
    
    for(int i=0;i<n;i++)
    cin>>a[i];
    
   findMajority(a, n);
    
}

Complexity Analysis: 

• Time Complexity: O(nlogn+n)  , as it requires O(nlogn) for sorting and O(n) to find the count of mid element
• Auxiliary Space : O(1). 

METHOD 3  (Using Moore’s Voting Algorithm): 

• Approach: This is a two-step process. 
  • The first step we should find the candidate for majority element, which may or may not be the majority element.
  • Check the above found candidate key is majority element or not. 
     
• Algorithm: 
1. Loop through each element and maintains a count of majority element, and a majority index, maj_index
2. If the next element is same then increment the count if the next element is not same then decrement the count.
3. if the count reaches 0 then changes the maj_index to the current element and set the count again to 1.
4. Now again traverse through the array and find the count of majority element found.
5. If the count is greater than half the size of the array, print the element
6. Else print that there is no majority element

implementation:

• #include <bits/stdc++.h>
  using namespace std;
  
  int findCandidate(int a[], int size)
  {
      int maj_index = 0, count = 1;
      for (int i = 1; i < size; i++) {
          if (a[maj_index] == a[i])
              count++;
          else
              count--;
          if (count == 0) {
              maj_index = i;
              count = 1;
          }
      }
      return a[maj_index];
  }
   
  /* Function to check if the candidate
     occurs more than n/2 times */
  bool isMajority(int a[], int size, int cand)
  {
      int count = 0;
      for (int i = 0; i < size; i++)
      {
          if (a[i] == cand)
              count++;
      }
      if (count > size / 2)
          return 1;
   
      else
          return 0;
  }
   
  /* Function to print Majority Element */
  void printMajority(int a[], int size)
  {
      /* Find the candidate for Majority*/
      int cand = findCandidate(a, size);
   
      /* Print the candidate if it is Majority*/
      if (isMajority(a, size, cand))
          cout << cand << endl;
   
      else
          cout << -1<<endl;
  }
  
   
  int main() 
  { 
      int n;
      cin>>n;
      int a[n];
      
      for(int i=0;i<n;i++)
      cin>>a[i];
      
      printMajority(a, n);
      
  }

Complexity Analysis: 

• Time Complexity: O(n).
  
• Auxiliary Space : O(1). 
  
  

METHOD 4 (Using UNORDERED MAP): 

• Algorithm:
1. Create a unordered_map to store a key-value pair, i.e. element-frequency pair.
2. Traverse the array from start to end ,for every element in the array, insert the element in the unorderd_map if the element does not exist as key, else fetch the value of the key ( array[i] ) and increase the value by 1
3. If the count is greater than half of the size of array then print the majority element and break.
4. If no majority element is found print -1
• 
  

implementation:

#include <bits/stdc++.h>
using namespace std;
 
void findMajority(int arr[], int size)
{
    unordered_map<int, int> m;
    for(int i = 0; i < size; i++)
        m[arr[i]]++;
    int count = 0;
    for(auto i : m)
    {
        if(i.second > size / 2)
        {
            count =1;
            cout << i.first<<endl;
            break;
        }
    }
    if(count == 0)
        cout << -1 << endl;
}

 
int main() 
{ 
    int n;
    cin>>n;
    int a[n];
    
    for(int i=0;i<n;i++)
    cin>>a[i];
    
    printMajority(a, n);
    
}

Complexity Analysis: 

• Time Complexity: O(n).
  
• Auxiliary Space : O(1).