Majority Element in an array

Naive Method

The most basic method is to use two loops and keep track of the total number of elements. Break the loops and return the element with the highest count if the maximum count exceeds n/2. The majority element does not exist if the maximum count does not exceed n/2.

Algorithm

• Create a variable count = 0 to keep the maximum count.
• From beginning to end, traverse the array.
• Run another loop for each element in the array to discover the count of similar elements in the given array.
• If the count exceeds the maximum count, increment the maximum count and save the index in a separate variable.
• Print the element if the maximum count is larger than half the array's size. 
• Otherwise, there is no majority element. 

The following code illustrates finding the majority element in an array in C++ :

#include <iostream>
using namespace std;
int main() {
    int arr[] = {8, 2, 2, 8, 1, 2, 2, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_frequency = 0;
    int index = -1;
    for (int i = 0; i < n; i++) {
        int frequency = 0;
        for (int j = 0; j < n; j++) {
            if (arr[i] == arr[j])
                frequency++;
        }
        if (frequency > max_frequency) //updating the max value
        {
            max_frequency = frequency;
            index = i;
        }
    }
    if (max_frequency > n / 2) // if max_frequency is greater than n/2 it prints the value
        cout << arr[index] << endl;
 
    else
        cout << "No Majority Element" << endl; //Prints if no majority element is found


    return 0;
}

Output: 

2

Complexity

Time complexity: O(n²)

Space Complexity: O(1) 

Try and compile by yourself with the help of online C++ Compiler for better understanding.

Using Sorting

The approach is to sort the data in the array. Similar items in the array are adjacent after sorting; therefore, traverse the array and update the count until the current element is similar to the preceding one. Print the majority element if the frequency is greater than half the array's size.

Algorithm

• Create a variable count and a variable prior, prev = INT_MIN, and sort the array.
• Follow the element from start to end.
• Increment the count if the current element is equal to the preceding element.
• Otherwise, set the count to 1
• If the count exceeds half of the array's size, print the element as the majority element and break.
• If there isn't a majority element, print "No majority element."

The following code illustrates finding the majority element in an array in C++ :

#include <bits/stdc++.h>
using namespace std;
int majorityElement(int *arr, int n)
{
    sort(arr, arr+n); // sorting array
    int count = 1, max_frequency = -1, temp = arr[0], element, flag=0;
    for(int i=1;i<n;i++)
    {
        if(temp==arr[i]) //counting the same elements
        {
            count++;
        }
        else
        {
            count = 1;
            temp = arr[i];
        }
        if(max_frequency<count)
        {
            max_frequency = count; //storing maximum frequency
            element = arr[i];
           
            if(max_frequency>(n/2)) //if max_frequency becomes > n/2 it breaks
            {
                flag = 1;
                break;
            }
        }
    }
    if(flag==1)
        return element; //returning the value of majority element found
    else
        return -1;
}
 
int main()
{
    int arr[] = {8, 2, 2, 8, 1, 2, 2, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<majorityElement(arr, n);
    return 0;
}

Output:

2

Complexity

Time complexity: O(nlogn)

Space Complexity: O(1) 

Also read, Application of Oops

Using Binary Search Tree

Insert elements one by one into BST, and if an element is already there, increase the node's count. If the count of a node reaches more than n/2 at any point, return.

Algorithm

• Create a binary search tree 
• If the same element is input multiple times in the binary search tree, the node's frequency increases.
• In the binary search tree, traverse the array and insert the entry.
• If any node's maximum frequency is larger than half the array's size, execute an inorder traversal to discover the node with the highest frequency.
• If there isn't a majority element, print "No majority element."

The following code illustrates finding the majority element in an array in C++ :

#include <bits/stdc++.h>
using namespace std;
 
struct node {
    int key;
    int c = 0;
    struct node *left, *right;
};
 
struct node* newNode(int item) //function for creating new node in a binary tree
{
    struct node* temp= (struct node*)malloc(sizeof(struct node));
    temp->key = item;
    temp->c = 1;
    temp->left = temp->right = NULL;
    return temp;
}
 
struct node* insert(struct node* node, int key, int& maximum) //function for inserting new node in a binary tree
{
    if (node == NULL) {
        if (maximum == 0)
            maximum = 1;
        return newNode(key); //return a new node , if the tree is empty
    }
 
    if (key < node->key)
        node->left = insert(node->left, key, maximum);
    else if (key > node->key)
        node->right = insert(node->right, key, maximum);
    else
        node->c++;
 
    maximum = max(maximum, node->c); //finding maximum element
    return node;
}
 
void inorder(struct node* root, int s) //function for inorder traversal of BST
{
    if (root != NULL) {
        inorder(root->left, s);
 
        if (root->c > (s / 2))
            printf("%d \n", root->key);
 
        inorder(root->right, s);
    }
}
int main()
{
    int a[] = {8, 2, 2, 8, 1, 2, 2, 6, 2};
    int size = (sizeof(a)) / sizeof(a[0]);
 
    struct node* root = NULL;
    int maximum = 0;
 
    for (int i = 0; i < size; i++)
    {
        root = insert(root, a[i], maximum);
    }
    if (maximum > (size / 2))
        inorder(root, size);
    else
        cout << "No majority element\n";
    return 0;
}

Output:

2

Complexity

Time complexity :O(n²)

Space Complexity : O(n) 

Using Hashmap

In the method, Maintain a count for each element(key) in Hashmap(key-value pair) at value, and whenever the count is larger than half the array length, return that key (majority element).

Algorithm

• Create a hashmap to store a key-value pair, such as an element-frequency pair.
• Traverse the array.
• If the element does not already exist as a key, insert it into the hashmap; otherwise, get the value of the key (array[i]) and increase the value by one.
• If the count exceeds half, print the majority element and then break.
• If there isn't a majority element, print "No Majority element."

The following code illustrates finding the majority element in an array in C++ :

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int arr[] = {8, 2, 2, 8, 1, 2, 2, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    unordered_map<int, int> m; //defining hashmap
    for(int i = 0; i < n; i++)
        m[arr[i]]++; //inserting elements in hashmap
    int count = 0;
    for(auto i : m)
    {
        if(i.second > n / 2) //printing the majority element
        {
            count =1;
            cout << i.first<<endl;
            break;
        }
    }
    if(count == 0)
        cout << "No Majority element" << endl;
    return 0;
}

Output:

2

Complexity

Time complexity: O(n)

Space Complexity: O(n) 

Check out this array problem - Merge 2 Sorted Arrays

Using Moore’s Voting Algorithm

This method consists of two methods :

• The first step assigns an element to the array that may be the majority element. If an array contains a majority element, this step will yield the majority element; otherwise, it will return a candidate for the majority element.
• Check to see if the element you got from the previous step is the majority element. This step is required since there may not be a majority element.

Algorithm

• Loop through each element, keeping a count of the majority element and a max index for the majority index.
• If the following element is the same as the previous one, the count should be increased. If the following element isn't the same as the previous one, the count is decremented.
• If the count approaches 0, adjust the count to 1 and modify the max index to the current element.
• Return to the array and count the number of majority elements discovered.
• Print the element if the count is larger than half the array's size.
• If there isn't a majority element, print "No Majority element."

The following code illustrates finding the majority element in an array in C++ :

#include <bits/stdc++.h>
using namespace std;
int findCandidate(int a[], int size) //finding candidate for majority
{
    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];
}
 
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) //if the element occurs more than n/2 times , it returns 1
        return 1;
 
    else
        return 0;
}
 
int main()
{
    int a[] = {8, 2, 2, 8, 1, 2, 2, 6, 2};
    int size = (sizeof(a)) / sizeof(a[0]);
    int cand = findCandidate(a, size);
    if (isMajority(a, size, cand)) //Checking whether the candidate element is majority or not.
        cout << cand;
    else
        cout << "No Majority Element";
    return 0;
}

Output:

2

Complexity

Time complexity :O(n)

Space Complexity : O(1) 

Try and compile by yourself with the help of online C++ Compiler for better understanding.

FAQs.

 

1. What is the Majority Element in an array? 
   The majority element in the array is the element that occurs n/2 times. (Here, n is the size of the array.)
    
2. For finding the majority element in an array, which method is efficient in terms of Time Complexity?
   Moore’s Voting Algorithm and Hashmap are efficient in terms of Time Complexity for finding the majority element in an array.
    
3. What is the Average Time Complexity for finding the majority element in an array using Hashmap?
   The Average Time Complexity for finding the majority element in an array using Hashmap is O(n).
    
4. What is the Average Time Complexity for finding the majority element in an array using a Binary Search Tree?
   The Average Time Complexity for finding the majority element in an array using a Binary Search Tree is O(n²).
    
5. What is the Average Time Complexity for finding the majority element in an array using Moore’s Voting Algorithm?
   The Average Time Complexity for finding the majority element in an array using Moore’s Voting Algorithm is O(n).

Key Takeaways

In this article, we have extensively discussed finding the majority element in an array and their implementation in C++. The article explains the different approaches used to find the majority element in an array. The use of the sorting, Binary Search Tree, Hashmap, Moore’s Voting Algorithm explained. There are many more approaches, but these are the most efficient in terms of time and space.

Recommended Topic: Array in Java

We hope that this blog has helped you enhance your knowledge regarding the reverse of string and if you would like to learn more, check out our articles on C++.

 Do upvote our blog to help other ninjas grow. 

Happy Coding!