Sunday, October 13, 2013

Finding the majority element of an array

Given an array of  N elements, the majority element is defined as the one which occurs more than N/2 times.

One simple approach is to find the mode (which appears for most number of times) and check if its frequency is greater than N/2.

Three strategies for finding the mode are discussed in my previous post. The best one among them, the hash map approach takes O(n) time and O(n) space.

We can solve this program even better by using Moore's voting algorithm. This takes O(n) time and O(1) space.

This algorithm tries to find out the majority number in two iterations. In the first iteration, a probable candidate for majority number is found. In second iteration, we check if the candidate is really the majority number by counting it's frequency.

The first iteration works as follows. We initialize the first element as the majority number and the count variable is initialized with 1. During further iterations, if the element is equal to majority number, we increment the count, otherwise we decrement the count. If at any point, the count reaches zero, We reassign the majority number to the current element and assign 1 to count.

For example, let us consider the input array {6, 2, 3, 6, 3, 6, 6, 6}. The following table explains the logic.

Iteration#12345678
Data62663616
Majority62666666
count11121212

At the end 6 is the candidate for majority number. In the second iteration we check the frequency of 6. If it is more than half of the array size it is the majority element.
 
Here is the Java implementation of this approach.