Majority element in array
Given an array of integer, find majority element in array. Element is called a majority element, if it is present in array more than half of total. For example, if there are n elements in array and if number X occurs more than n/2 times in array, then X is said to be majority element. If there is no such element, than we say that array does not contain any majority element. Below are some examples:
A = [2,2,4,3,2,6,2,7,2,2] Majority element : 2 occurs 6/10 A = [2,2,4,5,2,6,1,7,2,2] No majority element as 2 occurs 5/10 A = [2,4,4,2,1,1,6,7,2,6] No majority element as no elements has more than 5 occurances.
First of all, let’s think of some questions which one must ask to clarify problem statement. First, can array contain negative elements? Second, what can be possible range of numbers? Third, if a number occurs exactly n/2 times, should it be considered as majority elements? And last, what should be returned if there is no majority element?
First two questions show that before jumping to solution you care about nature of input provided. Third and fourth question show that you define clear contracts and function which can be used by dependent code as we will be returning what is expected from calling code.
Methods to find Majority element in array
Now that we have understood the problem clearly, let’s solve it.
What will be the brute force solution to find majority element? Solution will be to scan through each element, count occurrence of that in array and if that count is more than half of total elements, return that as majority element.
Complexity of above method is O(n2) which will be frowned upon by interviewer.
Sort the input set, and count occurrences of each element. It will be better than brute force now as we can break counting once different element is encountered.
Complexity is dependent on sorting method used. If correct sorting method (heap sort) is used, worst case complexity will be O(n log n). Apart from complexity, we are modifying original input, which may not go down well with interviewer.
This is were one of our questions asked will be helpful. If range of elements in array is limited,this method works well.
Define a hash which store count of each element in array. Scan through the entire array, update the count. While scanning, keep track of the highest occurring elements till that element. Once scanning finishes, check if highest occurring elements occurs more than half of all elements.
Complexity is O(N) but with a catch. If range of elements is too large, than space complexity will be too large to bear as space complexity is O(R) where R is range of elements.
Moore’s Majority Algorithm
This is efficient method to find majority elements in array. In this, we keep track of a pair, current candidate and current count. While scanning through elements, perform below two steps to get output:
When pointer forward over an element e: 1. If the counter is 0, we set the current candidate to e and we set the counter to 1. 2. If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.
Below figure explains the algorithm:
Implementation of Moore’s majority element algorithm
Complexity of Moore’s algorithm to find majority element in array is O(N) which O(1) space complexity.
Please share if there are suggestions to improve. Please share if you think this was helpful. Sharing is caring.