Majority Element - The Coding Shala
In this post, we will learn how to find Majority Element in the array and will implement its solution in Java.
Majority Element Problem
The majority element is the element that appears more than n / 2 times. You may assume that the majority element always exists in the array.
Majority Element Java Solution
First sort the array then find the frequency of elements, if the count is greater than n/2 return that.
Time Complexity: O(nlogn) [sorting]
We can use HashMap to store the counts of elements that will take additional O(n) space.
Modification in Sorting approach.
We know that the Majority element comes more than n/2 time. After sorting the array the middle element is always the Majority element.
Boyer-Moore Voting Algorithm. [Read Here]
Time Complexity: O(n)
Space Complexity: O(1)
- Move Zeroes
- Count Number of Inversions
- Sort an Array according to set bits
- How to find the second largest element in the array
- Find first duplicate in the array