Do you think IIT Guwahati certified course can help you in your career?
Introduction:
You will be given an array, and you need to find the Majority Element(An element that occurs more than N / 2 times in the array of N elements).
Let us see few examples:
Input: [1, 3, 3, 3, 6]
Output: 3
Explanation: The given array has 5 elements. And, since 3 occurs three times in the array, which is more than N / 2 (5 / 2 = 2), 3 is the majority element.
Input: [3, 5, 5, 6, 9]
Output: -1
Explanation: Since no element occurs more than N / 2 times, the output is -1.
Approach 1:
You can run two for loops and find the frequency of each element. If any element occurs more than N / 2 elements where ‘N’ is the number of elements in the array, you can break from the loops and return that majority element else, return -1.
Time Complexity: In the above approach, two nested for loops are used. Hence, the time complexity for the above approach is O(N * N).
Space Complexity: We haven’t used any auxiliary space in the above approach. Hence, the space complexity is O(1).
Approach 2:
We can use a HashMap to store the frequency of every element, and if at any point the frequency of any element is more than N / 2, we will find our Majority Element.
In the above approach, we run a for loop and keep updating the frequency of each element.
Time Complexity: Since we are running a single for loop, time complexity will be O(N).
Space Complexity: We are maintaining a HashMap to store the frequency of every element. Hence, the space complexity will be O(N).
Approach 3 (Moore’s Voting Algorithm):
This algorithm returns us an element that might be a majority element. So, whatever element this algorithm returns us, we need to check if it occurs more than N / 2 times or not.
Now let us see how this algorithm works:
We will maintain two things, ‘majorityIndex’ and ‘majorityCnt.’ (‘majorityIndex’ is the index of the expected majority element and ‘majorityCnt’ helps us in storing the count of the majority element).
Initially, ‘majorityIndex’ will be 0, and ‘majorityCnt’ will be 1.
We will start traversing our array from index 1. If the current element is the same as the element present at the 'majorityIndex,' we will increment ‘majorityCnt’ by one else decrement it by one.
If at any point ‘majorityCnt’ becomes zero. We will change the ‘majorityIndex’ to be the current index and ‘majorityCnt’ to be 1.
After traversing the entire array, the element present at the ‘majorityIndex’ might be the majority element.
In the end, we will just check if the frequency of the element present at ‘majorityIndex’ is more than N / 2 or not.
Implementation:
#include <bits/stdc++.h> usingnamespacestd; // Function to find the candidate for Majority intfindCandidate(int a[], int size) { int majorityIndex = 0, majorityCnt = 1; for (int i = 1; i < size; i++) { if (a[majorityIndex] == a[i]){ majorityCnt++; } else{ majorityCnt--; } if (majorityCnt == 0) { majorityIndex = i; majorityCnt = 1; } } return a[majorityIndex]; } /* Function to check if the candidate occurs more than n/2 times */ boolisMajority(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){ return1; } else{ return0; } } // Function to print Majority Element voidprintMajority(int a[], int size) { // Find the candidate for Majority int majorityElement = findCandidate(a, size); // Print the candidate if it is Majority if (isMajority(a, size, majorityElement)){ cout << " " << majorityElement << " "; } else{ cout << "No Majority Element"; } } intmain() { int a[] = { 1, 3, 3, 3, 2 }; int size = (sizeof(a)) / sizeof(a[0]); // Function calling printMajority(a, size); return0; }
Output:
3
Time Complexity: The time complexity for the above implementation is O(N) because we run only two loops. One for loop to find the possible majority element and second for loop to check if that element is present more than N / 2 times.
Space Complexity: Space complexity for the above implementation is O(1) because we are not using auxiliary space.
What is the intuition behind this algorithm? If the element is present more than N / 2 times in the array, its count will never become zero.
Is there a need to confirm that the element returned to us by Moore’s voting algorithm is Majority Element or not? Yes, you need to iterate and check the frequency of that number because it might be possible that there is no Majority Element, but still, the algorithm will return you any element.
What part makes this algorithm efficient?
The concept to keep incrementing and decrementing the ‘majorityCnt’ helps us solve it efficiently. Since the frequency of the Majority Element is always more than N / 2, the ‘majorityCnt’ for that element will always remain positive.
Key Takeaways:
In this blog, we have covered the following things:
We first discussed two approaches to find the Majority Element.
Then we saw how we optimized the approach to O(N) time complexity and O(1) space complexity using Moore’s voting algorithm.
If you want to learn more about Arrays and practice some questions requiring you to take your basic knowledge on Arrays a notch higher, you can visit our Guided Path for Arrays. To practice this problem, you can see Practice Majority Element Problem.
137+ registered 
