Category: Easy
Problem
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exists in the array.
https://leetcode.com/problems/majority-element/description/
Examples
Example 1:
1 2 | Input: [3,2,3] Output: 3 |
Example 2:
1 2 | Input: [2,2,1,1,1,2,2] Output: 2 |
Solution Approach
In this problem, we have to find the element which is repeated more than half of the length of the array. This is a pretty straightforward question but the application of the concepts used to solve this problem can be of more importance.
I will use three techniques to solve this very problem with different time complexities. Although any one of the three can be used it’s better to know all the solutions so that they can aid us in future problems and complexities are very important even if the question is easy.
Sorting
The simple and most obvious method to go about this problem is to sort the elements and get the middle element as the answer as the problem clearly states that the majority element will always exist. We are sorting the elements so that the middle element will always be a majority element. The time complexity of solving this problem will be O(nlogn) as it takes nlogn time to sort the array. No extra space is required hence the s[pace complexity is O(1).
Coming to the code part of the solution we just sort the array using the sort() method and return the middle element as the answer.
Hash map
This is again a simple method to solve the problem where we just have to iterate through the array only one time but to store the values we require extra space. We are saving the frequency of all the elements in the hash map. At the same time as saving the frequency, we have to save a counter which will keep track of the element with the greatest frequency till now. The time complexity is O(n) as array iteration is done only once but the space complexity increases to O(n) concerning the previous solution as overhead is required to save the key-value pair.
Coming to the code part of this approach we initialize a Hashmap to store the frequency map along with the count variable to store the greatest frequency and we also initialise a variable to store the key whose value is maximum. We then iterate through the array and store the mapping by using the getOrDefault method of hashmap. Then we iterate over the keys of the map and try to find the frequency with the maximum value by comparing it with the previously maximum frequency and at the end, we store the maximum frequency in count variable and the corresponding key in majokey variable. We return the majorkey as the answer.
Boyer-Moore Voting Algorithm
This is a special algorithm which is an offset of the above approach but we are not storing the values in a hashmap because we know ultimately that the number which is in majority will be more than half. We iterate through the array only once and we check the elements while iterating hence the time complexity is only O(n) and there is no need to have a lot of space to store the values. We just need 2 variables one to store the count of the current major element and the other to store that major element itself which needs to be returned as the answer.
For the code of this approach, we take 2 variables as discussed above called major and count and initialise them with 0. Then we loop over the whole array and we place the value of the element to the major variable if the count is 0. Otherwise, we increment the count variable by 1 is we encounter the major element as the array element. If that is not the case we decrement the count value by 1. In the end, we return the value stored in the major variable as our answer.
Solution code
Sorting
1 2 3 4 5 6 | class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; } } |
Hash map
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution { public int majorityElement(int[] nums) { int majorkey = 0, count = 0; Map<Integer, Integer> map = new HashMap<>(); for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1); for (int key : map.keySet()) { if (map.get(key) > count) { count = map.get(key); majorkey = key; } } return majorkey; } } |
Boyer-Moore Voting Algorithm
1 2 3 4 5 6 7 8 9 10 11 | class Solution { public int majorityElement(int[] nums) { int major = 0, count = 0; for (int i = 0; i < nums.length; i++) { if (count == 0) major = nums[i]; if (major == nums[i]) count++; else count--; } return major; } } |
For more Leetcode explained solutions visit Leetcode Solutions. If you like capture the flag challenges visit here.
Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via Contact page I will surely respond. Happy Leetcoding