Majority Element - How to Find?

We have been given an integer array of size ‘n’, we have to print the majority element of the given array and, if no majority element exists then we need to print “No majority element exists.” The majority element is defined as the element which occurs more than n/2 times in the array. It can be easily observed that at max, 1 majority element can exist for a particular array.

Example 1-

Input - a[] = {5, 8, 3, 5, 5, 2, 5}
Output - 5

Explanation - 5 appears 4 times and as 4>(7/2) we conclude that 5 is our majority element.

Example 2 -

Input - a[]={9, 3, 2, 9, 5}
Output - No majority element exists.

Explanation - We can observe that no element is occurring more than n/2 i.e. 2 times.

Simple Approach (Brute Force)

The idea is to count the frequency of every element by running two nested loops and if we find any element repeating more than n/2 times then we print that and break our loops. If even after traversing the whole array we didn’t find any majority element we simply print “No majority element exists.” Below is the implementation of the above approach -

C++ Programming

#include <bits/stdc++.h>
using namespace std;
void printMajoriyElementIfExists(int a[],int n){
    
    // Outer loop to
    // traverse the array.
    for(int i=0;i<n;i++)
    {
        int count=0;
        // Inner loop to
        // count frequency 
        // of a[i]. 
        for(int j=i;j<n;j++) { if(a[j]==a[i]) count++; } // If count>n/2
        // it means a[i]
        // is a Majority element.
        if(count>n/2)
        {
            cout<<a[i]<<" is the Majority element.";
            return;
        }
    }
    
    // If execution reaches here 
    // it means no Majority element exists.
    cout<<"No Majority element exists.";
    
}
int main() {
	int arr[] = {5, 8, 3, 5, 5, 2, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    printMajoriyElementIfExists(arr,n);
    
    cout<<endl;
	return 0;
}

Output:

5 is the Majority element.

Java Programming

import java.util.*;
public class Main{
    public static void printMajoriyElementIfExists(int a[],int n){
        
        // Outer loop to
        // traverse the array.
        for(int i=0;i<n;i++)
        {
            int count=0;
            // Inner loop to
            // count frequency 
            // of a[i]. 
            for(int j=i;j<n;j++) 
            { 
               if(a[j]==a[i]) 
                  count++; 
            } 
            // If count>n/2
            // it means a[i]
            // is Majority element.
            if(count>n/2)
            {
                System.out.print(a[i]+" is the Majority element.");
                return;
            }
        }
        
        // If execution reaches here 
        // it means no Majority element exists.
        System.out.print("No Majority element exists.");
        
    }
    public static void main(String[] args){
 
        int arr[] = {5, 8, 3, 5, 5, 2, 5};
        int n = arr.length;
        
        printMajoriyElementIfExists(arr,n);
        
        System.out.println();
    }    
}

Output:

5 is the Majority element.

Python Programming

def printMajoriyElementIfExists(arr, n):
 
    # Outer loop to
    # traverse the array.
    for i in range(n):
 
        count = 0
        # Inner loop to
        # count frequency 
        # of a[i]. 
        for j in range(n):
 
            if(arr[i] == arr[j]):
                count +=1
 
        # If count>n/2
        # it means a[i]
        # is Majority element.
        if (count > n/2):
            print(arr[i], "is the Majority element.")
            return
    # If execution reaches here 
    # it means no Majority element exists.
    print("No Majority Element exists.")
 
 
# Driver code
if __name__ == "__main__":
    arr = [5, 8, 3, 5, 5, 2, 5]
    n = len(arr)
 
    # Function calling
    printMajoriyElementIfExists(arr, n)
    print()

Output:

5 is the Majority element.

Complexity Analysis

• Time Complexity : O(n^2), Because in the worst case we have to make n^2 operations.
• Extra Space : O(1), Since we didn't use any extra space.

Another Approach

In this approach, the idea of sorting is used. We can observe that after sorting equal elements become adjacent. For an example array - {5, 8, 3, 5, 5, 2, 5} becomes {2, 3, 5, 5, 5, 5, 8}. Have a look at the algorithm for better understanding -

Algorithm:

1. Sort the given array.
2. Create a variable freq to store the frequency of an element, initialize it with 1.
3. Traverse array from 1 to n-1.
4. If the current element is equal to the previous element then we will increase our freq else we will make freq=1.
5. During each iteration, we will check if freq>n/2 then we will print the current element as the majority element.
6. At last, if we didn’t encounter any majority element then we will print no majority element exists.

Below is the implementation of the above approach -

C++ Programming

#include <bits/stdc++.h>
using namespace std;
void printMajoriyElementIfExists(int a[],int n){
        // If size of array is 
        // 1 then the first element
        // is a Majority element.
        if(n==1)
        {
            cout<<a[0]<<" is the Majority element.";
            return;
        }
        
        // Sort the array.
        sort(a,a+n);
        // Initialize freq with 1.
        int freq=1;
        for(int i=1;i<n;i++) 
        { 
            // If previous element 
            // is equal to current 
            // increase freq. else // make it 1. 
            if(a[i]==a[i-1]) 
               freq++; 
            else 
               freq=1; 
            // If freq>n/2 at
            // any point of time.   
            // it means it is Majority
            // element.
            if(freq>n/2)
            {
                cout<<a[i]<<" is the Majority element.";
                return;
            }
        }
        
        cout<<"No Majority element exists.";
    
}
int main() {
	int arr[] = {5, 8, 3, 5, 5, 2, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    printMajoriyElementIfExists(arr,n);
    
    cout<<endl;
	return 0;
}

Output:

5 is the Majority element.

JAVA:

import java.util.*;
public class Main{
    public static void printMajoriyElementIfExists(int a[],int n){
        // If size of array is 
        // 1 then the first element
        // is Majority element.
        if(n==1) 
        {
            System.out.print(a[0]+ " is the Majority element.");
            return;
        }
        
        // Sort the array.
        Arrays.sort(a);
        // Initialize freq with 1.
        int freq=1;
        for(int i=1;i<n;i++) 
        { 
            // If previous element 
            // is equal to current 
            // increase freq. else 
            // make it 1. 
            if(a[i]==a[i-1]) 
                freq++; 
            else 
                freq=1; 
            // If freq>n/2 at
            // any point of time.   
            // it means it is Majority
            // element.
            if(freq>n/2)
            {
                System.out.print(a[i]+ " is the Majority element.");
                return;
            }
        }
        
        System.out.print("No Majority element exists.");
        
    }
    public static void main(String[] args){
 
        int arr[] = {5, 8, 3, 5, 5, 2, 5};
        int n = arr.length;
        
        printMajoriyElementIfExists(arr,n);
        
        System.out.println();
        
    }    
}

Output:

5 is the Majority element.

Python Programming

def printMajoriyElementIfExists(arr, n) :
    # If size of array is 
    # 1 then the first element
    # is a Majority element.
    if(n==0):
        print(arr[0], "is the Majority element.")
        return
    # Sort the array.
    arr.sort()  
    #  Initialize freq with 1.
    freq=1
    for i in range(1, n) :
         
        # If previous element
        # is equal to current
        # increase freq. else
        # make it 1.
        if(arr[i-1] == arr[i]) :
            freq += 1
        else :
            freq = 1
        # If freq>n/2 at
        # any point of time.   
        # it means it is Majority
        # element.
        if(freq>n/2):
            print(arr[i], "is the Majority element.")
            return
             
    print("No Majority element exists.")
 
# Driver code
if __name__ == "__main__":
    arr = [5, 8, 3, 5, 5, 2, 5]
    n = len(arr)
 
    # Function calling
    printMajoriyElementIfExists(arr, n)
    print()

Output:

5 is the Majority element.

Complexity Analysis

• Time Complexity: O(nlogn). Since sorting takes O(n log n) time.
• Extra Space: O(1). Since no extra space is required.

Efficient Approach

In this idea we will use hashing, a HashMap to be exact. We can store the frequency of each element in our HashMap by traversing the array once. And during another traversal, we can print the element with a frequency of more than n/2. Have a look at the algorithm for better understanding -

Algorithm:

1. Create a HashMap
2. Traverse the array, and update the frequency of elements each time.
3. Again traverse the array from 0 to n-1.
4. If any element’s frequency is greater than n/2 print it.
5. If we did not find any majority element it means the array does not contain any majority element.

Below is the implementation of above approach -

C++ Programming

#include <bits/stdc++.h>
using namespace std;
void printMajoriyElementIfExists(int a[],int n){
        // Create a HashMap
        unordered_map<int, int> hm;
        // Find frequency of each element.
        for(int i=0;i<n;i++)
        {
            hm[a[i]]++;
        }
        // Check if any element's
        // frequency is greater
        // than n/2.
        for(int i=0;i<n;i++) 
        { 
            auto temp=hm.find(a[i]); 
            if(temp->second>n/2)
            {
                cout<<a[i]<<" is the Majority element.";
                return;
            }
        }
        cout<<"No Majority element exists.";
    
}
int main() {
	int arr[] = {5, 8, 3, 5, 5, 2, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    printMajoriyElementIfExists(arr,n);
    
    cout<<endl;
	return 0;
}

Output:

5 is the Majority element.

Java Programming

import java.util.*;
public class Main{
    public static void printMajoriyElementIfExists(int a[],int n){
        
        // Create a HashMap
        HashMap<Integer,Integer> hm=new HashMap<>();
        
        // Find frequency of each element.
        for(int i=0;i<n;i++) 
        {
            hm.put(a[i],hm.get(a[i])==null?1:hm.get(a[i])+1);
        }
        
        // Check if any element's
        // frequency is greater
        // than n/2.
        for(int i=0;i<n;i++) 
        { 
            if(hm.get(a[i])>n/2)
            {
                System.out.print(a[i]+" is the majority element.");
                return;
            }
        }
        System.out.print("No majority element exists.");
        
    }
    public static void main(String[] args){
 
        int arr[] = {5, 8, 3, 5, 5, 2, 5};
        int n = arr.length;
        
        printMajoriyElementIfExists(arr,n);
        
        System.out.println();
        
    }    
}

Output:

5 is the Majority element.

Python Programming

def printMajoriyElementIfExists(a, n) :
    # Create a HashMap
    m = {}
    # Find frequency of each element.
    for i in range(n):
        if a[i] in m:
            m[a[i]] += 1
        else:
            m[a[i]] = 1
    # Check if any element's
    # frequency is greater
    # than n/2.
    for key in m:
        if m[key] > n / 2:
            print(a[i], "is the Majority element.")
            return
    
    print("No Majority element exists.")
 
# Driver code
if __name__ == "__main__":
    arr = [5, 8, 3, 5, 5, 2, 5]
    n = len(arr)
 
    # Function calling
    printMajoriyElementIfExists(arr, n)
    print()

Output:

5 is the Majority element.

Complexity Analysis:

• Time Complexity: O(n). Since only two traversals of the array are needed.
• Auxiliary Space : O(n). Since a hashmap is used.

Optimal Approach

This approach is based on Moore’s Voting algorithm. This involves two steps: in the first step we check for a potential element that can be our answer and in step 2 we will check if that element is a majority element or not. Let’s look at the algorithm to have a better understanding -

Algorithm:

1. To check for potential elements, we will maintain two variables i.e. ‘ind’ and ‘freq’, and initialize them with 0 and 1.
2. We will traverse the array if a[ind]=a[i] we will increase our freq else we will decrease it. Once freq reaches zero we will update freq and ind with 1 and i respectively.
3. After traversing we have a[ind] as our potential answer.
4. Now we will check if a[ind] is actually our answer or not.
5. If it is then we will print that element as our majority element otherwise we can conclude no majority element exists in the array.

Below is the implementation of above approach -

C++ Programming:

#include <bits/stdc++.h>
using namespace std;
int findPotentialAnswer(int a[],int n){
        
    // Initialize ind and
    // freq with 0 and 1.
    int ind=0,freq=1;
    for(int i=0;i<n;i++)
    {
        // Increase freq
        // if condition statisfy.
        if(a[i]==a[ind])
        {
            freq++;
        }
        else
        freq--;
        
        // If freq==0
        // then change accordingly. 
        if(freq==0)
        {
            freq=1;
            ind=i;
        }
    }

    return a[ind];
}
void printMajoriyElementIfExists(int a[],int n){
    // Find the potential_answer.
    int potential_answer=findPotentialAnswer(a,n);
    
    // Check whether the
    // potential_answer is
    // actually Majority
    // element or not.
    int count=0;
    for(int i=0;i<n;i++) 
    { 
        if(a[i]==potential_answer) 
          count++; 
    } 
    // If count>n/2
    // it means that it 
    // is the Majority element.
    if(count>n/2)
    cout<<potential_answer<<" is the Majority element.";
    else
    cout<<"No Majority element exists.";
       
    
}
int main() {
	int arr[] = {5, 8, 3, 5, 5, 2, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    printMajoriyElementIfExists(arr,n);
    
    cout<<endl;
	return 0;
}

Output:

5 is the Majority element.

Java Programming

import java.util.*;
public class Main {
    public static void printMajoriyElementIfExists(int a[],int n){
        
        // Find the potential_answer.
        int potential_answer=findPotentialAnswer(a,n);
        
        // Check wether the
        // potential_answer is
        // actually Majority
        // element or not.
        int count=0;
        for(int i=0;i<n;i++) 
        {
        if(a[i]==potential_answer) 
           count++; 
        } 
        // If count>n/2
        // it means that it 
        // is the Majority element.
        if(count>n/2)
        System.out.print(potential_answer+" is the Majority element.");
        else
        System.out.print("No Majority element exists.");
    }
    public static int findPotentialAnswer(int a[],int n){
        
        // Initialize ind and
        // freq with 0 and 1.
        int ind=0,freq=1;
        for(int i=0;i<n;i++)
        {
            // Increase freq
            // if condition statisfy.
            if(a[i]==a[ind])
            {
                freq++;
            }
            else
            freq--;
            
            // If freq==0
            // then change accordingly. 
            if(freq==0)
            {
                freq=1;
                ind=i;
            }
        }
    
        return a[ind];
    }
	public static void main (String[] args) {
		int arr[] = {5, 8, 3, 5, 5, 2, 5};
        int n = arr.length;
        
        printMajoriyElementIfExists(arr,n);
    	System.out.println();
	
	}
}

Output:

5 is the Majority element.

Python Programming:

def findPotentialAnswer(A):
    # Initialize ind and
    # freq with 0 and 1.
    ind = 0
    freq = 1
    for i in range(len(A)):
        # Increase freq
        # if condition statisfy.
        if A[ind] == A[i]:
            freq += 1
        else:
            freq -= 1
        # If freq==0
        # then change accordingly. 
        if freq == 0:
            ind = i
            freq = 1
    return A[ind]
 
def isMajority(A, cand):
    count = 0
    # If count>n/2
    # it means that it 
    # is the Majority element.
    for i in range(len(A)):
        if A[i] == cand:
            count += 1
    if count > len(A)/2:
        return True
    else:
        return False

def printMajoriyElementIfExists(arr):
    # Find the potential_answer.
    potential = findPotentialAnswer(arr)
 
    # Print the potential if it is Majority
    if isMajority(arr, potential) == True:
        print(potential, "is the Majority Element.")
    else:
        print("No Majority Element exists")
 
 
# Driver code
arr = [5, 8, 3, 5, 5, 2, 5]
printMajoriyElementIfExists(arr)

Output:

5 is the Majority element.

Complexity Analysis:

• Time Complexity : O(n), Since only two traversals of the array, is needed.

• Extra Space : O(1), Because we only used variables.

Wrapping Up!

In this article, we have learned how to find the “Majority Element”. We discussed four approaches in which we can solve this problem. It also contains well-explained codes of both the approaches in the three most popular languages which are C++, Java, and Python, and their respective outputs are attached to the article for a better understanding of a wide range of our readers. We sincerely hope that this article has walked you through some deep and important concepts of Arrays, Hashing, and sorting and you have learned how we should approach such kinds of problems. We hope that you will now be able to solve this problem as well as its other variations seamlessly and efficiently.

Happy Coding!

People are also reading:

• How to find and remove loops in a Linked List?
• Find the minimum jumps required to reach the destination
• Difference Between Repeater, DataList, and GridView
• DSA: Hashing
• Bellman-Ford Algorithm
• AVL Tree
• DSA: Binary Heap Tree
• Fibonacci Series
• Circular Doubly Linked List