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

Output-1

Explanation

9 appears 5 times which is more than n/2, half of the size of the array size.

Input-2

Output-2

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

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++

Code in Java

Code in Python

Output

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++

Code in Java

Code in Python

Output

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++

Code in Java

Code in Python

Output

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++

Code in Java

Code in Python

Output

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++

Code in Java

Code in Python

Output

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++

Code in Java

Code in Python

Output

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.