Given an array of size n, Write a code to find majority element in an array.
What is Majority Element?
The majority element is the element that appears more than n/2 times where n is the size of an array.
NOTE: For this problem you can assume that the array is non-empty and the majority element always exist in the array.
Example 1:
Input : [3, 2, 3]
Output: 3
The size of the array is 3 and the element which occurs more than 1 is the majority element. So three is the output.
Example 2:
Input: [2, 2, 1, 1, 1, 2, 2]
Output: 2
The element 2 occurs more than 3 times. So, It is the majority element.
To solve this problem, we start with the easiest approach and then we will improve our solution.
Method 1 – Brute Force Approach
The easiest approach is to run two for loops to check whether any element of an array appears more than n/2 times.
The time complexity of this approach is O(n^2) and it’s space complexity is O(1).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
//Solution using two for loops public int majorityElementBruteForce(int[] nums) { //Majority count is n/2 int majorityCount = nums.length/2; //Outer loop for(int i = 0; i < nums.length; i++) { int count = 0; //Inner loop for(int j = 0; j < nums.length; j++) { if(nums[i] == nums[j]) { count++; } } //If count is greater than n/2 if(count > majorityCount) { return nums[i]; } } return -1; } |
How we can improve our solution? Let’s improve our solution using HashMap.
Remove duplicates from unsorted array
Find Majority Element in an Array using HashMap
We can solve this problem in a single traversal using HashMap.
Here are the following steps –
i) First we have to create a map of number and it’s count using HashMap.
ii) Then, we can traverse the map and check the element which has count greater than n/2.
The time complexity of this approach is O(n) and it’s space complexity is O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
//Majority Element using HashMap public Integer majorityElementUsingMap(int[] nums) { int majorityCount = nums.length/2; //Declare map Map<Integer, Integer> elemCountMap = new HashMap<>(); //Traverse an array, to count number and it's occurrences for(int i = 0; i < nums.length; i++) { //Element is key and it occurrences is it's value elemCountMap.put(nums[i], elemCountMap.getOrDefault(nums[i], 0) + 1); } /* Traverse a map and check the element which has count greater than n/2. */ for(Map.Entry<Integer, Integer> record : elemCountMap.entrySet()) { if(record.getValue() > majorityCount) { return record.getKey(); } } return -1; } |
Using HashMap we have solved the problem in single traversal but we have used extra space. Can we find the majority element without using any extra space?
Find Majority Element in an Array using Boyer-Moore Majority Vote Algorithm
Using Boyer-Moore majority vote algorithm we can find the majority element without using any extra space.
This algorithm finds the majority element if it exists. The first step is to find the candidate for majority element. Then next step is to verify whether this candidate element is the majority element or not.
In this problem, It is already given that majority element always exist in the input array. So we don’t need to verify them. To start with this algorithm we need two variables one for count and other for candidate. When count is zero the current element is the candidate element.
Initially, the value of count is zero and candidate is null. When we start traversing an array the first element is the candidate element. Now, we have to compare candidate element with element present at current index. If it is same then we have to increment the count else we have to decrement it. When the value of count is zero, consider the current element as the candidate element. After complete traversal of an array we get the majority element.
The time complexity of this approach is O(n) and it’s space complexity is O(1).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
//Find Majority Element using Boyer-Moore Majority Vote Algorithm public static Integer majorityElement(int[] nums) { int count = 0; Integer candidate = null; for(int i = 0; i < nums.length; i++) { if(count == 0) { candidate = nums[i] } count += (candidate == nums[i]) ? 1 : -1; } return candidate; } |
Majority Element InterviewBit Solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
//Majority Element InterviewBit Solution public class Solution { public int majorityElement(final List<Integer> A) { int count = 0; Integer candidate = null; for(int i = 0; i < A.size(); i++) { if(count == 0) { candidate = A.get(i); } count += (candidate.equals(A.get(i))) ? 1 : -1; } return candidate; } } |
