1. Home
  2. Majority Element Using Sorting

Majority Element Using Sorting

The idea is to sort the array. Sorting makes similar elements in the array adjacent, so traverse the array and update the count until the present element is similar to the previous one. If the frequency is more than half the size of the array, print the majority element.

Illustration:

arr[] = {3, 4, 3, 2, 4, 4, 4, 4}, n = 8

Array after sorting => arr[] = {2, 3, 3, 4, 4, 4, 4, 4}, count = 1

At i = 1:

  • arr[i] != arr[i – 1] => arr[1] != arr[0]
  • count is not greater than n/2, therefore reinitialise count with, count = 1

At i = 2:

  • arr[i] == arr[i – 1] => arr[2] == arr[1] = 3
  • count = count + 1 = 1 + 1 = 2

At i = 3

  • arr[i] != arr[i – 1] => arr[3] != arr[2]
  • count is not greater than n/2, therefore reinitialise count with, count = 1

At i = 4

  • arr[i] == arr[i – 1] => arr[4] == arr[3] = 4
  • count = count + 1 = 1 + 1 = 2

At i = 5

  • arr[i] == arr[i – 1] => arr[5] == arr[4] = 4
  • count = count + 1 = 2 + 1 = 3

At i = 6

  • arr[i] == arr[i – 1] => arr[6] == arr[5] = 4
  • count = count + 1 = 3 + 1 = 4

At i = 7

  • arr[i] == arr[i – 1] => arr[7] == arr[6] = 4
  • count = count + 1 = 4 + 1 = 5
  • Therefore, the count of 4 is now greater than n/2.

Hence, 4 is the majority element.

Follow the steps below to solve the given problem:

  • Sort the array and create a variable count and previous, prev = INT_MIN.
  • Traverse the element from start to end.
  • If the current element is equal to the previous element increase the count.
  • Else set the count to 1.
  • If the count is greater than half the size of the array, print the element as the majority element and break.
  • If no majority element is found, print “No majority element”

Below is the implementation of the above idea: 

C++ 
// C++ program to find Majority 
// element in an array
#include <bits/stdc++.h>
using namespace std;

// Function to find Majority element
// in an array
// it returns -1 if there is no majority element

int majorityElement(int *arr, int n)
{
    if (n == 1) return arr[0];
    
    int cnt = 1;
      // sort the array, o(nlogn)
    sort(arr, arr + n);
    for (int i = 1; i <= n; i++){
        if (arr[i - 1] == arr[i]){
            cnt++;
        }
        else{
            if (cnt > n / 2){
                return arr[i - 1];
            }
            cnt = 1;
        }
    }
    // if no majority element, return -1
    return -1;
}


// Driver code
int main()
{
    int arr[] = {1, 1, 2, 1, 3, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    // Function calling 
    cout<<majorityElement(arr, n);

    return 0;
}
Java 
// Java program to find Majority  
// element in an array 
import java.io.*;
import java.util.*;

class GFG{

// Function to find Majority element 
// in an array it returns -1 if there
// is no majority element   
public static int majorityElement(int[] arr, int n)
{
    
    // Sort the array in O(nlogn)
    Arrays.sort(arr);

    int count = 1, max_ele = -1, 
         temp = arr[0], ele = 0,
            f = 0;

    for(int i = 1; i <= n; i++)
    {
        
        // Increases the count if the 
        // same element occurs otherwise
        // starts counting new element
        if (temp == arr[i])
        {
            count++;
        }
        else 
        {
            count = 1;
            temp = arr[i];
        }

        // Sets maximum count and stores
        // maximum occurred element so far
        // if maximum count becomes greater
        // than n/2 it breaks out setting
        // the flag
        if (max_ele < count) 
        {
            max_ele = count;
            ele = arr[i];

            if (max_ele > (n / 2)) 
            {
                f = 1;
                break;
            }
        }
    }

    // Returns maximum occurred element
    // if there is no such element, returns -1
    return (f == 1 ? ele : -1);
}

// Driver code 
public static void main(String[] args)
{
    int arr[] = { 1, 1, 2, 1, 3, 5, 1 };
    int n = 7;

    System.out.println(majorityElement(arr, n));
}
}

// This code is contributed by RohitOberoi
Python 
# Python3 program to find Majority 
# element in an array

# Function to find Majority element
# in an array
# it returns -1 if there is no majority element
def majorityElement(arr, n) :
    
    # sort the array in O(nlogn)
    arr.sort()   
    count, max_ele, temp, f = 1, -1, arr[0], 0
    for i in range(1, n) :
        
        # increases the count if the same element occurs
        # otherwise starts counting new element
        if(temp == arr[i]) :
            count += 1
        else :
            count = 1
            temp = arr[i]
            
        # sets maximum count
        # and stores maximum occurred element so far
        # if maximum count becomes greater than n/2
        # it breaks out setting the flag
        if(max_ele < count) :
            max_ele = count
            ele = arr[i]
            
            if(max_ele > (n//2)) :
                f = 1
                break
            
    # returns maximum occurred element
    # if there is no such element, returns -1
    if f == 1 :
        return ele
    else :
        return -1

# Driver code
arr = [1, 1, 2, 1, 3, 5, 1]
n = len(arr)

# Function calling 
print(majorityElement(arr, n))

# This code is contributed by divyeshrabadiya07
C# 
// C# program to find Majority  
// element in an array 
using System;
class GFG
{

// Function to find Majority element 
// in an array it returns -1 if there
// is no majority element   
public static int majorityElement(int[] arr, int n)
{
    
    // Sort the array in O(nlogn)
    Array.Sort(arr);

    int count = 1, max_ele = -1, 
         temp = arr[0], ele = 0,
            f = 0;

    for(int i = 1; i < n; i++)
    {
        
        // Increases the count if the 
        // same element occurs otherwise
        // starts counting new element
        if (temp == arr[i])
        {
            count++;
        }
        else 
        {
            count = 1;
            temp = arr[i];
        }

        // Sets maximum count and stores
        // maximum occurred element so far
        // if maximum count becomes greater
        // than n/2 it breaks out setting
        // the flag
        if (max_ele < count) 
        {
            max_ele = count;
            ele = arr[i];

            if (max_ele > (n / 2)) 
            {
                f = 1;
                break;
            }
        }
    }

    // Returns maximum occurred element
    // if there is no such element, returns -1
    return (f == 1 ? ele : -1);
}

// Driver code 
public static void Main(String[] args)
{
    int []arr = { 1, 1, 2, 1, 3, 5, 1 };
    int n = 7;
    Console.WriteLine(majorityElement(arr, n));
}
}

// This code is contributed by aashish1995
Javascript 
<script>

    // Javascript program to find Majority 
    // element in an array
    
    // Function to find Majority element
    // in an array it returns -1 if there
    // is no majority element  
    function majorityElement(arr, n)
    {

        // Sort the array in O(nlogn)
        arr.sort(function(a, b){return a - b});

        let count = 1, max_ele = -1,
             temp = arr[0], ele = 0,
                f = 0;

        for(let i = 1; i < n; i++)
        {

            // Increases the count if the
            // same element occurs otherwise
            // starts counting new element
            if (temp == arr[i])
            {
                count++;
            }
            else
            {
                count = 1;
                temp = arr[i];
            }

            // Sets maximum count and stores
            // maximum occurred element so far
            // if maximum count becomes greater
            // than n/2 it breaks out setting
            // the flag
            if (max_ele < count)
            {
                max_ele = count;
                ele = arr[i];

                if (max_ele > parseInt(n / 2, 10))
                {
                    f = 1;
                    break;
                }
            }
        }

        // Returns maximum occurred element
        // if there is no such element, returns -1
        return (f == 1 ? ele : -1);
    }
    
    let arr = [ 1, 1, 2, 1, 3, 5, 1 ];
    let n = 7;
    document.write(majorityElement(arr, n));

</script>

Time Complexity: O(nlogn), Sorting requires O(n log n) time complexity.
Auxiliary Space: O(1), As no extra space is required.



Majority Element

Find the majority element in the array. A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element). 

Examples : 

Input : A[]={3, 4, 2, 4, 2, 4, 4}
Output : 4
Explanation: The frequency of 4 is greater than the half of the size of the array size. 

Input : A[] = {3, 3, 4, 2, 4, 4, 2, 4}
Output : No Majority Element
Explanation: There is no element whose frequency is greater than the half of the size of the array size.

Recommended Practice
Majority Element
Try It!

Similar Reads

Naive Approach:

The basic solution is to have two loops and keep track of the maximum count for all different elements. If the maximum count becomes greater than n/2 then break the loops and return the element having the maximum count. If the maximum count doesn’t become more than n/2 then the majority element doesn’t exist....

Majority Element Using Moore’s Voting Algorithm:

This is a two-step process: The first step gives the element that may be the majority element in the array. If there is a majority element in an array, then this step will definitely return majority element, otherwise, it will return candidate for majority element.Check if the element obtained from the above step is the majority element. This step is necessary as there might be no majority element....

Majority Element using Binary Search Tree

Insert elements in BST one by one and if an element is already present then increment the count of the node. At any stage, if the count of a node becomes more than n/2 then return....

Majority Element Using Hashing:

In Hashtable(key-value pair), at value, maintain a count for each element(key), and whenever the count is greater than half of the array length, return that key(majority element)....

Majority Element Using Sorting:

The idea is to sort the array. Sorting makes similar elements in the array adjacent, so traverse the array and update the count until the present element is similar to the previous one. If the frequency is more than half the size of the array, print the majority element....

Categories

HTML CSS3 Bootstrap Foundation Sass JavaScript TypeScript JQuery AngularJS React NodeJS Highcharts PHP Python Python3 Django Linux Docker Ruby Java C C ++ Perl Servlet JSP Lua Scala Go ASP C # SQL MySQL SQLite MongoDB Redis Android Swift ionic Kotlin XML tutorial

Contact US