Finding the Majority element in an array
November 4, 2010 1 Comment
In its simplest terms, the Majority element is the element that occurs the most within a given array of numbers. Here, we mean by “the most” that the number of occurrences of the element must be more than half the size of the array. In mathematical terms, given an unsorted array of integers from 1 to n, where n is the length of the array, an element is a Majority if it occurs at least (n/2) + 1 times.
The Majority element is an important problem in computer science and is used as a basis for more complex algorithms. We also encounter the majority element in our daily life. For example, the ownership of a large company is determined by shareholders having more than half the total share. Another example is the elections in your country where the winner is determined by obtaining more than half the voices.
In this article, we will look at a fast algorithm that runs in linear time, in exactly O(n) + O(n) to find the Majority element. The algorithm was discovered by Rengakrishnan Subramanian in December 2001. His official paper can be found here.
The algorithm approaches the problem in two steps, in the first step we will call the method FindElement that takes an array of integers as an input and returns an element that is “most likely” to be Majority. In the second step, the algorithm will call FindMajority which takes the same array as an input along with the most probable element we determined earlier and will return the element if it turns out to be Majority, or null if its not.
The FindElement algorithm works as follows:
1-declare two variables, we’ll call the first one count and the second one canbeMajority to store the candidate Majority.
2-assume that the first number in the array is Majority and assign its value to canbeMajority.
3-traverse the input array from start to end while applying the following conditions:
- If the next element in the array is equal to canbeMajority, then count is incremented by 1.
- If the next element in the array is not equal to canbeMajority, then count is decremented by 1.
- If at the next element, the count is equal to zero, then count is set to one and this element is considered as canbeMajority
Here is the implementation of FindElement and FindMajority in vb.net:
Private Function FindElement(ByRef arr() As Integer) As Integer Dim count As Integer = 0 Dim element As Integer = 0 For i As Integer = 0 To arr.Length - 1 If count = 0 Then count = 1 element = arr(i) ElseIf arr(i) = element Then count += 1 Else count -= 1 End If Next Return element End Function Private Function FindMajority(ByRef arr() As Integer) As Integer Dim element As Integer = FindElement(arr) Dim count As Integer = 0 For i As Integer = 0 To arr.Length - 1 If arr(i) = element Then count += 1 Next If count > arr.Length / 2 Then Return element Else Return Nothing End Function
I have created a simple application that reads or generates arbitrary array of numbers and find its Majority but I will leave the implementation of the application as an exercise to the reader :). However you can compare your results with mine by looking at the picture below