Majority Element in an Array

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

1. Initialize a variable maxCount to store the max count and the count for the current count and set it to 0.
2. Using for loop traverse through the arr[] array and find the count of each element in the array.
3. Update the maxCount if the count exceeds the maximum count, and store the index in a index variable.
4. If the maxCount is more than n/2, half of the size of the array size then return the array element.
5. 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

1. Create a BST, Traverse through the array and start inserting elements of the array one by one.
2. If any element entered is already present in the binary search tree then increase the frequency of the node.
3. Whenever the maximum frequency of any node exceeds n/2, then find the node with maximum frequency by performing inorder traversal.
4. 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

1. Traverse through the array and keep track of the count and the index of the majority element.
2. Increment the count if the next element is the same. Decrement the count if the next element is different.
3. Whenever the count becomes 0, change the index of the majority element to the current element and set the count to 1 again.
4. Finally, traverse through the array once again and find the count of the majority element from the previous steps.
5. If the count is more than n/2, half of the size of the array size then return the array element.
6. 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

1. Create a Hashmap(key-value pair) to store the element as well their frequency.
2. Traverse through the array elements and put all the elements in the hashmap if the map does not already contain it.
3. Else if the map already contains the key (element) then increment the value of the key arr[i] by 1.
4. Also check if the count is more than n/2, half of the size of the array size then break.
5. 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

1. At first, sort the array and initialize the variables to keep track of count and previous element.
2. Traverse through all the elements of the given array.
3. Increment the count if the current element equals the previous element. Else set the count to one.
4. Also check if the count is more than n/2, half of the size of the array size then break.
5. 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

1. Initialize a variable majorityElement to store the majority element and set its value to 0.
2. Now run a loop from currBit = 0 to 31, where the variable currBit represents the current bit position of a 32-bit integer.
3. Initialize a variable count for each bit position to count the frequency of 1’s and set its value to 0.
4. Now traverse through the array elements and increment count by 1 if the current bit position is 1.
5. 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.
6. 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