Find the majority element in an array
Difficulty Level: Medium
Asked in: Microsoft, Google, Amazon, Yahoo
Understanding the Problem
Problem Description: You are given an array A[] consisting of n elements. You need to find and return the number which appears more than n/2 times.
Note: Do not confuse the majority element as just the element with maximum frequency. A majority element occurs more than n/2 times.
For example :
Input: A[] = {3,9,1,3,5,3,3}
Output: 3
Input: A[] = {8,8,8,8,8,10,10}
Output: 8
Possible questions to ask the interviewer:-
- Is an element a majority element if it appears exactly n/2 times? ( Ans: No, the majority element needs to appear more than n/2 times)
- What should I return if there is no majority element? ( Ans: In that case, return -1, assume that “-1” will never be an element in the input array)
Solutions
We will be discussing five possible solutions for this problem:-
- Brute Force Approach: Using two nested loops
- Using Sorting
- Using Hash Table
- Bit Manipulation algorithm
- Boyer-Moore Majority Vote Algorithm
1. Brute Force Approach : Using two nested loops
A simple brute force approach for this problem would be to use nested loops and count the frequency of each element. If we reach an element with a frequency greater than n/2, that’s our majority element.
Pseudo-Code
int findMajorityElement(int A[], int n)
{
for ( i = 0 to n-2 )
{
int count = 1
for ( j = i+1 to n-1 )
{
if ( A[i] == A[j] )
count = count + 1
}
if ( count > n/2 )
return A[i]
}
return -1
}
Complexity Analysis
Time Complexity: O(n²) ( Why? )
Space Complexity: O(1)
Critical ideas to think!
- How can we improve the time complexity of finding the frequency of an element?
- What is the best-case input and what will be the time complexity in that case?
2. Using Sorting
If we sort the array, all similar elements will line up next to each other, it is now easy to check the frequency of each element and can be done in linear time.
Pseudo-Code
int findMajorityElement(int A[], int n)
{
sort(A, n)
int i = 1, count = 1
while ( i < n )
{
while ( i < n and A[i] == A[i-1] )
{
i = i + 1
count = count + 1
}
if ( count > n/2 )
return A[i-1]
count = 1
i = i + 1
}
return -1
}
Complexity Analysis
Time Complexity: Sorting the array + Linear Traversal (Each element is visited only once) = O(nlogn) + O(n) = O(nlogn)
Space Complexity: If we use merge sort, then O(n), else if we use Heap Sort, its O(1)
Critical ideas to think!
- How should we use extra space to improve our time complexity of finding the frequency of all elements?
3. Using Hash Table
If we create an auxiliary Hash Table which will store the frequency of each element in linear time and space complexity. We could then traverse the Hash Table and see if any element has a frequency greater than n/2.
Pseudo-Code
int findMajorityElement(int A[], int n)
{
Create a HashTable H
for ( i = 0 to n-1 )
{
if ( A[i] in H )
H[A[i]] = H[A[i]] + 1
else
H[A[i]] = 1
if ( H[A[i]] > n/2 )
return A[i]
}
return -1
}
Complexity Analysis
Time Complexity: O(n) ( Why? )
Space Complexity: O(n), for storing the auxiliary Hash Table
Critical ideas to think!
- Can this problem be solved via a Binary Search Tree using similar logic? What will be the time and space complexity then?
4. Bit Manipulation Algorithms
In this approach, we will deal with the binary representation of the numbers. The algorithm first determines the frequency of each bit in the input array. If there is a number with a majority in the input (i.e. it makes up more than half of the input), then the frequency of all its set bits will be in the majority, and the frequency of all its unset bits will be in the minority.
Solution Steps
We shall be assuming that the elements in the array are within the confines of a 32-bit integer.
- Create a loop to iterate from 0 to 32 representing the current bit position.
- For each bit position, initialize a variable count = 0
- Now iterate the entire array and increase count by 1 if the current bit position is set in an element. ( How to check if the bit at certain position is 1 or 0?)
- If the resultant count is greater than n/2, set this bit position in the majority element. ( How do you set a bit at a particular position?)
- Check the count of the majority element formed by a linear traversal of the array and return it if the count is greater than n/2, else return -1.
Pseudo-Code
int findMajorityElement(int A[], int n)
{
int majority_element = 0, count = 0
for ( curr = 0 to 32 )
{
count = 0
for ( i = 0 to n-1 )
{
// Checks if the bit no. 'curr' is set or not in A[i]
if ( A[i] & (1<<curr) )
count = count + 1
}
if ( count > n/2 )
{
// Setting the bit no. 'curr' as 1 in the majority element
majority_element += (1 << curr)
}
}
count = 0
for( i = 0 to n-1 )
if ( A[i] == majority_element )
count += 1
if ( count > n/2 )
return majority_element
else
return -1
}
Complexity Analysis
Time Complexity: Checking each bit position for entire array + Finding frequency of majority_element = O(32*n) + O(n) = O(n)
Space Complexity: O(1)
Critical ideas to think!
- What element will be formed if a majority element does not exist?
- What other problems can you solve using similar bit manipulation logic?
5. Boyer-Moore Majority Vote Algorithm
The Boyer-Moore Majority Vote Algorithm finds the majority element if it's guaranteed that the majority element exists. We will just check the frequency of the element found by this algorithm in the end to confirm.
The intuition in the algorithm is that since the majority element occurs more than n/2 times, its frequency is greater than all other elements combined. Therefore, for each occurrence of the majority element, we can cross out one non-majority element.
Solution Steps
- Initialize a max_index = 0 and count = 0. The element at index max_index is considered to be our current candidate for majority element.
- Traverse the array updating max_index and count according to the following conditions:-
- If A[max_index] == A[i], increase count by 1.
- Else, decrease count by 1.
- If count == 0, max_index = i and count = 1.
3. Check the frequency of the element at max_index via a linear traversal of the array
Pseudo-Code
int findMajorityElement(int A[], int n)
{
int max_index = 0, count = 0
for( i = 0 to n-1 )
{
if ( A[i] == A[max_index] )
count += 1
else
count -= 1
if ( count == 0 )
{
max_index = i
count = 1
}
}
count = 0
for ( i = 0 to n-1 )
if ( A[i] == A[max_index] )
count += 1
if ( count > n/2 )
return A[max_index]
else
return -1
}
Complexity Analysis
Time Complexity: Linear traversal of array + Finding frequency of A[max_index] = O(n) + O(n) = O(n)
Space Complexity: O(1)
Critical ideas to think!
- If a majority element does not exist, will A[max_index] represent element with maximum frequency?
Comparison of different solutions
Suggested Problems to solve
- Find if any element repeats more than N/3 times
- Check if an array has a majority element
- Find majority element in a circular array of 0’s and 1’s
- Sort elements based on their frequency
- Find the element with the second-largest frequency
If you have any more approaches or you find an error/bug in the above solutions, please comment down below.
Happy Coding! Enjoy Algorithms!