Problem Statement
You are given an array arr[] containing n integers including duplicates. Write a program to find the majority element in an array if it is present. Else print no Majority Element Found. An element is called a majority element when it appears more than n/2 times in an array of length n.
Example
Input-1
arr[] : [9, 4, 3, 9, 9, 4, 9, 9, 8]
Output-1
9
Explanation
9 appears 5 times which is more than n/2, half of the size of the array size.
Input-2
arr[] : [2, 4, 3, 6, 7, 5]
Output-2
No Majority Element Found
Explanation
In the given array, there is no element exists that appears more than n/2, half of the size of the array length.
Constraints
1 <= n <= 5 * 10^4
-10^9 <= nums[i] <= 10^9
Algorithm 1 – Brute-Force Approach – Using Two Nested Loops
Intuition:
The naive approach is to use two loops and track the maximum count for all elements. Break the for loops if the maximum count becomes greater than n/2 and return the element with the maximum count. The majority element does not exist if the maximum count does not become more than n/2.
Algorithm
- Initialize a variable maxCount to store the max count and the count for the current count and set it to 0.
- Using for loop traverse through the arr[] array and find the count of each element in the array.
- Update the maxCount if the count exceeds the maximum count, and store the index in a index variable.
- If the maxCount is more than n/2, half of the size of the array size then return the array element.
- Else there is no majority element that exists.
Code Implementation
Code in C++
// Brute-Force approach to find majority element in an array
#include <bits/stdc++.h>
using namespace std;
// Function to find Majority element
// in an array
void majorityElement(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 element
if (maxCount > n / 2)
cout << arr[index] << endl;
else
cout << "No Majority Element Found" << endl;
}
// Main method
int main()
{
int arr[] = { 9, 4, 3, 9, 9, 4, 9, 9, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
// call the function
majorityElement(arr, n);
return 0;
}
Code in Java
// Brute-Force approach to find majority element in an array
import java.io.*;
class Main {
static void majorityElement(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 element
if (maxCount > n / 2)
System.out.println(arr[index]);
else
System.out.println("No Majority Element Found");
}
// Main method
public static void main(String[] args){
int arr[] = { 9, 4, 3, 9, 9, 4, 9, 9, 8 };
int n = arr.length;
// Call the function
majorityElement(arr, n);
}
}
Code in Python
# Brute-Force approach to find majority element in an array
def majorityElement(arr, n):
maxCount = 0
index = -1
for i in range(n):
count = 0
for j in range(n):
if(arr[i] == arr[j]):
count += 1
# 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 element
if (maxCount > n//2):
print(arr[index])
else:
print("No Majority Element Found")
# Main method
if __name__ == "__main__":
arr = [9, 4, 3, 9, 9, 4, 9, 9, 8]
n = len(arr)
# Call the function
majorityElement(arr, n)
Output
9
Time Complexity
The time complexity is O(n^2). Since there are two nested loops that traverse the array.
Space Complexity
The space complexity is O(1). Since no extra space is used in the Program to Find majority element in an array.
Algorithm 2 – Using Divide and Conquer (Binary Search Tree)
Intuition:
Add elements in Binary Search Tree one by one and if any element is already there, increase the node’s count. Whenever a node’s count exceeds n/2 (half of the size of the array) then simply return.
Algorithm
- Create a BST, Traverse through the array and start inserting elements of the array one by one.
- If any element entered is already present in the binary search tree then increase the frequency of the node.
- Whenever the maximum frequency of any node exceeds n/2, then find the node with maximum frequency by performing inorder traversal.
- Else there is no majority element that exists.
Code Implementation
Code in C++
// Divide and Conquer approach to find majority element in an array
#include <bits/stdc++.h>
using namespace std;
struct node {
int key;
int c = 0;
struct node *left, *right;
};
// Function to create a Binary Search Tree node
struct node* newNode(int item)
{
struct node* temp
= (struct node*)malloc(sizeof(struct node));
temp->key = item;
temp->c = 1;
temp->left = temp->right = NULL;
return temp;
}
// Function to insert a node with a given key in the BST
struct node* insert(struct node* node, int key, int& ma)
{
// If the tree is empty, return a new node
if (node == NULL) {
if (ma == 0)
ma = 1;
return newNode(key);
}
// Otherwise, recur down the tree
if (key < node->key)
node->left = insert(node->left, key, ma);
else if (key > node->key)
node->right = insert(node->right, key, ma);
else
node->c++;
// find the max count
ma = max(ma, node->c);
// return the node pointer
return node;
}
// Inorder traversal of BST
void inorder(struct node* root, int s)
{
if (root != NULL) {
inorder(root->left, s);
if (root->c > (s / 2))
printf("%d \n", root->key);
inorder(root->right, s);
}
}
// Main method
int main()
{
int arr[] = { 9, 4, 3, 9, 9, 4, 9, 9, 8};
int size = (sizeof(arr)) / sizeof(arr[0]);
struct node* root = NULL;
int ma = 0;
for (int i = 0; i < size; i++) {
root = insert(root, arr[i], ma);
}
// Call the Function
if (ma > (size / 2))
inorder(root, size);
else
cout << "No majority element Found\n";
return 0;
}
Code in Java
// Divide and Conquer approach to find majority element in an array
import java.io.*;
class Node{
int key;
int c = 0;
Node left,right;
}
class Main{
static int max = 0;
// Function to create a Binary Search Tree node
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.c = 1;
temp.left = temp.right = null;
return temp;
}
// Function to insert a node with a given key in the BST
static Node insert(Node node, int key)
{
// If the tree is empty, return a new node
if (node == null)
{
if (max == 0)
max = 1;
return newNode(key);
}
// Otherwise, recur down the tree
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else
node.c++;
// Find the max count
max = Math.max(max, node.c);
// Return the node pointer
return node;
}
// Inorder traversal of Binary Search Tree
static void inorder(Node root, int s)
{
if (root != null)
{
inorder(root.left, s);
if (root.c > (s / 2))
System.out.println(root.key + "\n");
inorder(root.right, s);
}
}
// Driver Code
public static void main(String[] args){
int arr[] = { 9, 4, 3, 9, 9, 4, 9, 9, 8 };
int size = arr.length;
Node root = null;
for(int i = 0; i < size; i++)
{
root = insert(root, arr[i]);
}
// Function call
if (max > (size / 2))
inorder(root, size);
else
System.out.println("No majority element found\n");
}
}
Code in Python
# Divide and Conquer approach to find majority element in an array
class Node():
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.count = 1 # count of number of times data is inserted in tree
class BST():
def __init__(self):
self.root = None
def insert(self, data, n):
out = None
if (self.root == None):
self.root = Node(data)
else:
out = self.insertNode(self.root, data, n)
return out
def insertNode(self, currentNode, data, n):
if (currentNode.data == data):
currentNode.count += 1
if (currentNode.count > n//2):
return currentNode.data
else:
return None
elif (currentNode.data < data):
if (currentNode.right):
self.insertNode(currentNode.right, data, n)
else:
currentNode.right = Node(data)
elif (currentNode.data > data):
if (currentNode.left):
self.insertNode(currentNode.left, data, n)
else:
currentNode.left = Node(data)
# Main code
arr = [9, 4, 3, 9, 9, 4, 9, 9, 8]
n = len(arr)
# declaring None tree
tree = BST()
flag = 0
for i in range(n):
out = tree.insert(arr[i], n)
if (out != None):
print(arr[i])
flag = 1
break
if (flag == 0):
print("No Majority Element Found")
Output
9
Time Complexity
The time complexity is O(n^2). Since we created a binary search tree to find majority element in an array.
Space Complexity
The space complexity is O(n). Since extra space is used in the Program to store the array in a BST.
Algorithm 3 – Efficient Approach – Using Moore’s Voting Algorithm
Intuition:
Since A majority element is an element that appears more than n/2 times, the frequency of the majority is more than the frequency of all other elements together. Hence, we can increment the count of the majority element and decrement the count of any other element, after that the sum of all the elements in an array should be greater than zero.
Algorithm
- Traverse through the array and keep track of the count and the index of the majority element.
- Increment the count if the next element is the same. Decrement the count if the next element is different.
- Whenever the count becomes 0, change the index of the majority element to the current element and set the count to 1 again.
- Finally, traverse through the array once again and find the count of the majority element from the previous steps.
- If the count is more than n/2, half of the size of the array size then return the array element.
- Else there is no majority element that exists.
Code Implementation
Code in C++
// Efficient approach to find majority element in an array
#include <bits/stdc++.h>
using namespace std;
/* Function to find Majority Element */
int findMajority(int arr[], int n)
{
int index = 0, count = 1;
for (int i = 1; i < n; i++) {
if (arr[index] == arr[i])
count++;
else
count--;
if (count == 0) {
index = i;
count = 1;
}
}
return arr[index];
}
/* Function to check if the candidate
occurs more than n/2 times */
bool isMajority(int arr[], int n, int majorityElement)
{
int count = 0;
for (int i = 0; i < n; i++)
if (arr[i] == majorityElement)
count++;
if (count > n / 2)
return 1;
else
return 0;
}
/* Function to print Majority Element */
void printMajority(int arr[], int n)
{
/* Call the function*/
int majorityElement = findMajority(arr, n);
/* Print the Majority Element*/
if (isMajority(arr, n, majorityElement))
cout << majorityElement;
else
cout << "No Majority Element Found";
}
/* Main method */
int main()
{
int arr[] = { 9, 4, 3, 9, 9, 4, 9, 9, 8 };
int n = (sizeof(arr)) / sizeof(arr[0]);
// Function calling
printMajority(arr, n);
return 0;
}
Code in Java
// Efficient approach to find majority element in an array
class Main {
// Function to find the Majority Element
int findCandidate(int arr[], int n){
int index = 0, count = 1;
int i;
for (i = 1; i < n; i++) {
if (arr[index] == arr[i])
count++;
else
count--;
if (count == 0) {
index = i;
count = 1;
}
}
return arr[index];
}
// Function to check if the candidate occurs more than n/2 times
boolean isMajority(int arr[], int n, int majorityElement)
{
int i, count = 0;
for (i = 0; i < n; i++) {
if (arr[i] == majorityElement)
count++;
}
if (count > n / 2)
return true;
else
return false;
}
// Function to print the Majority Element
void printMajority(int arr[], int n)
{
// Calling the function
int majorityElement = findCandidate(arr, n);
/* Print the candidate if it is Majority*/
if (isMajority(arr, n, majorityElement))
System.out.println(majorityElement);
else
System.out.println("No Majority Element Found");
}
// Main method
public static void main(String[] args)
{
Main majorityElement
= new Main();
int arr[] = new int[] { 9, 4, 3, 9, 9, 4, 9, 9, 8 };
// Function call
int n = arr.length;
majorityElement.printMajority(arr, n);
}
}
Code in Python
# Efficient approach to find majority element in an array
# Function to check if the majority element occurs more than n/2 times
def isMajority(arr, majorityElement):
count = 0
for i in range(len(arr)):
if arr[i] == majorityElement:
count += 1
if count > len(arr)/2:
return True
else:
return False
# Function to find the majority element
def findCandidate(arr):
index = 0
count = 1
for i in range(len(arr)):
if arr[index] == arr[i]:
count += 1
else:
count -= 1
if count == 0:
index = i
count = 1
return arr[index]
# Function to print Majority Element
def printMajority(arr):
# Find the candidate for Majority
majorityElement = findCandidate(arr)
# Print the candidate if it is Majority
if isMajority(arr, majorityElement) == True:
print(majorityElement)
else:
print("No Majority Element Found")
# Main code
arr = [9, 4, 3, 9, 9, 4, 9, 9, 8]
# Function call
printMajority(arr)
Output
9
Time Complexity
The time complexity is O(n). Since we are traversing the array only two times. So the Complexity becomes linear.
Space Complexity
The space complexity is O(1). Since no extra space is used in the Program to Find majority element in an array.
Algorithm 4 – Using Hashmap
Intuition:
We can easily find majority element in an array by using a Hashmap(key-value pair), simply maintain a count at value for every key (element) and whenever the value exceeds half of the size of the array, return the majority element (key).
In terms of time complexity, this method is somewhat similar to the above Moore’s voting algorithm, but the second step of the Moore voting algorithm is not required in this case. however, space complexity here becomes O(n).
Algorithm
- Create a Hashmap(key-value pair) to store the element as well their frequency.
- Traverse through the array elements and put all the elements in the hashmap if the map does not already contain it.
- Else if the map already contains the key (element) then increment the value of the key arr[i] by 1.
- Also check if the count is more than n/2, half of the size of the array size then break.
- If we reach the end of the array then there is no majority element exists.
Code Implementation
Code in C++
// Hashmap approach to find majority element in an array
#include <bits/stdc++.h>
using namespace std;
void majorityElement(int arr[], int n)
{
unordered_map<int, int> map;
for(int i = 0; i < n; i++)
map[arr[i]]++;
int count = 0;
for(auto i : map)
{
if(i.second > n / 2)
{
count =1;
cout << i.first <<endl;
break;
}
}
if(count == 0)
cout << "No Majority element Found" << endl;
}
// Main method
int main()
{
int arr[] = {9, 4, 3, 9, 9, 4, 9, 9, 8};
int n = sizeof(arr) / sizeof(arr[0]);
// Call the function
majorityElement(arr, n);
return 0;
}
Code in Java
// Hashmap approach to find majority element in an array
import java.util.HashMap;
class Main
{
private static void majorityElement(int[] arr)
{
HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < arr.length; i++) {
if (map.containsKey(arr[i])) {
int count = map.get(arr[i]) +1;
if (count > arr.length /2) {
System.out.println(arr[i]);
return;
} else
map.put(arr[i], count);
}
else
map.put(arr[i],1);
}
System.out.println(" No Majority element Found");
}
// Main method
public static void main(String[] args)
{
int arr[] = new int[]{9, 4, 3, 9, 9, 4, 9, 9, 8};
majorityElement(arr);
}
}
Code in Python
# Hashmap approach to find majority element in an array
def majorityElement(arr, size):
m = {}
for i in range(size):
if arr[i] in m:
m[arr[i]] += 1
else:
m[arr[i]] = 1
count = 0
for key in m:
if m[key] > size / 2:
count = 1
print(key)
break
if(count == 0):
print("No Majority element Found")
# Main code
arr = [9, 4, 3, 9, 9, 4, 9, 9, 8]
n = len(arr)
# Call the function
majorityElement(arr, n)
Output
9
Time Complexity
The time complexity is O(n). Since we are traversing the array only one time. So the Complexity becomes linear.
Space Complexity
The space complexity is O(n). Since a HashMap is used in the Program to Find majority element in an array.
Algorithm 5 – Using Sorting
Intuition:
The intuition is to simply sort the given array. When elements are sorted, the array’s nearby similar elements become adjacent, allowing you to traverse the array and update the count until the current element is similar to the previous one. Print the majority element if the frequency is greater than the half of the size of the array.
Algorithm
- At first, sort the array and initialize the variables to keep track of count and previous element.
- Traverse through all the elements of the given array.
- Increment the count if the current element equals the previous element. Else set the count to one.
- Also check if the count is more than n/2, half of the size of the array size then break.
- If we reach the end of the array then there is no majority element exists.
Code Implementation
Code in C++
// Sorting approach to find majority element in an array
#include <bits/stdc++.h>
using namespace std;
// Function to find the Majority element
int majorityElement(int *arr, int n)
{
if (n == 1) return arr[0];
int count = 1;
// sort the array
sort(arr, arr + n);
for (int i = 1; i <= n; i++){
if (arr[i - 1] == arr[i]){
count++;
}
else{
if (count > n / 2){
return arr[i - 1];
}
count = 1;
}
}
return -1;
}
// Main method
int main(){
int arr[] = {9, 4, 3, 9, 9, 4, 9, 9, 8};
int n = sizeof(arr) / sizeof(arr[0]);
// Call the function
cout<<majorityElement(arr, n);
return 0;
}
Code in Java
// Sorting approach to find majority element in an array
import java.io.*;
import java.util.*;
class Main{
public static int majorityElement(int[] arr, int n){
// First Sort the array
Arrays.sort(arr);
int count = 1, max_element = -1,
temp = arr[0], element = 0,
flag = 0;
for(int i = 1; i <= n; i++){
// Increment the count if the element occurs again else
if (temp == arr[i])
count++;
else {
// Else set count to element
count = 1;
temp = arr[i];
}
// if maximum count becomes greater than n/2, break
if (max_element < count) {
max_element = count;
element = arr[i];
if (max_element > (n / 2)) {
flag = 1;
break;
}
}
}
return (flag == 1 ? element : -1);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 9, 4, 3, 9, 9, 4, 9, 9, 8 };
int n = 7;
System.out.println(majorityElement(arr, n));
}
}
Code in Python
# Sorting approach to find majority element in an array
def majorityElement(arr, n) :
# sort the array
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
if(temp == arr[i]) :
count += 1
else :
count = 1
temp = arr[i]
# sets maximum count
if(max_ele < count) :
max_ele = count
ele = arr[i]
if(max_ele > (n//2)) :
f = 1
break
# returns maximum occurred element
if f == 1 :
return ele
else :
return -1
# Main code
arr = [9, 4, 3, 9, 9, 4, 9, 9, 8 ]
n = len(arr)
# Call the Function
print(majorityElement(arr, n))
Output
9
Time Complexity
The time complexity is O(nlogn). Since we are using Arrays.sort function which requires O(nlogn) time complexity as it uses merge sort.
Space Complexity
The space complexity is O(1). Since no extra space is used in the Program to Find majority element in an array.
Algorithm 6 – Bit Manipulation Approach
Intuition:
This approach deals with the binary representation of numbers. The algorithm starts by determining the frequency of each bit in the input array. The frequency of all of a number’s set bits will be in the majority, and the frequency of all of its unset bits will be in the minority if the number has a majority in the input (i.e. it makes up more than half of the size of the array).
Algorithm
- Initialize a variable majorityElement to store the majority element and set its value to 0.
- Now run a loop from currBit = 0 to 31, where the variable currBit represents the current bit position of a 32-bit integer.
- Initialize a variable count for each bit position to count the frequency of 1’s and set its value to 0.
- Now traverse through the array elements and increment count by 1 if the current bit position is 1.
- In the end, if the variable count value is greater than n/2, then set the current bit position in the majorityElement variable. Else, leave it because the bit at that position has been already set to 0 in the variable majorityElement.
- Return the value of majorityElement variable.
Code Implementation
Code in C++
// Bit Manipulation approach to find majority element in an array
#include <iostream>
using namespace std;
void findMajority(int arr[], int n){
// Number of bits in the integer
int len = sizeof(int) * 8;
// Variable to calculate majority element
int number = 0;
// Loop to iterate through all the bits of number
for (int i = 0; i < len; i++) {
int count = 0;
// Loop to iterate through all elements in array
// to count the total set bit
for (int j = 0; j < n; j++) {
if (arr[j] & (1 << i))
count++;
}
// If the total set bits exceeds n/2,
// this bit should be present in majority Element.
if (count > (n / 2))
number += (1 << i);
}
int count = 0;
// iterate through array get
// the count of candidate majority element
for (int i = 0; i < n; i++)
if (arr[i] == number)
count++;
// Verify if the count exceeds n/2
if (count > (n / 2))
cout << number;
else
cout << "No Majority Element Found";
}
// Main method
int main(){
int arr[] = { 9, 4, 3, 9, 9, 4, 9, 9, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
findMajority(arr, n);
return 0;
}
Code in Java
// Bit Manipulation approach to find majority element in an array
class Main {
public static int majorityElement(int[] arr) {
int[] bitmask = new int[32], temp = new int[32];
// Prepping bit masks for 32 bit numbers
int mask = 1;
for (int bix=0; bix<32; bix++) {
bitmask[bix] = mask;
mask *= 2;
}
// Counting the popularity of bit "0" for each position
for (int nix=0; nix<arr.length; nix++) {
for (int bix=0; bix<32; bix++) {
if ((bitmask[bix] & arr[nix]) == 0) temp[bix]++;
else temp[bix]--;
}
}
// Recreate the majority element from the most popular bits
int mel = 0;
for (int bix=0; bix<32; bix++) {
if (temp[bix] < 0) mel += bitmask[bix];
}
return mel;
}
public static void main(String[] args)
{
int arr[] = { 9, 4, 3, 9, 9, 4, 9, 9, 8 };
int n = 7;
System.out.println(majorityElement(arr));
}
}
Code in Python
# Bit Manipulation approach to find majority element in an array
def findMajority(arr, n):
# Number of bits in the integer
Len = 32
# Variable to calculate majority element
number = 0
# Loop to iterate through
# all the bits of number
for i in range(Len):
count = 0
# Loop to iterate through all elements
# in array to count the total set bit
# at position i from right
for j in range(n):
if (arr[j] & (1 << i)):
count += 1
# If the total set bits exceeds n/2,
# this bit should be present in
# majority Element.
if (count > (n // 2)):
number += (1 << i)
count = 0
# iterate through array get
# the count of candidate majority element
for i in range(n):
if (arr[i] == number):
count += 1
# Verify if the count exceeds n/2
if (count > (n // 2)):
print(number)
else:
print("No Majority Element Found")
# Main Code
arr = [9, 4, 3, 9, 9, 4, 9, 9, 8 ]
n = len(arr)
findMajority(arr, n)
Output
9
Time Complexity
The time complexity is O(nlogn). Where n N time is taken to iterate all the elements of the array and logn is the time taken by the number of bits of an integer.
Space Complexity
The space complexity is O(1). Since no extra space is used in this Program to Find majority element in an array.
Conclusion
- We have given an array arr[] containing n integers including duplicates. We have to find majority element in an array if it exists. Otherwise print no Majority Element Found.
- A majority element is an element that appears more than n/2 times in an array of size n.
- For eg, an array arr[] = [9, 4, 3, 9, 9, 4, 9, 9, 8] is given, Here 9 appears five times which is more than n/2, half of the size of the array size.
- If there is no element present in the array whose frequency is more than n/2, then simply print No Majority Element Found.
- The brute force approach takes O(n^2) time complexity as two loops were used, and O(1) space complexity because no extra space was used.
- On the other hand, the most efficient approach to Find majority element in an array using Moore’s Voting Algorithm takes O(n) time complexity and O(1) as space complexity.
FAQ
Q: How to Find if any element repeats more than N/3 times in an array?
A. Refer N/3 repeated number in an array with O(1) space
Q: How to Find majority element in a circular array of 0’s and 1’s?
A. Refer Majority element in a circular array