Finding the Majority element in an array


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

MajorityElement

MajorityElement

One Response to Finding the Majority element in an array

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: