Given an array of n number, find the majority element (if any)?
(Majority element is the one which occurs more than n/2 number of times)
Example: A = [20, 4, 4, 7, 4, 16, 20, 4, 0, 4, 4], n = 11, '4' occurs 6 times, is the majority elemet.
How to go about it? Simplest method follows. Keep another array of counts and keep track of which number occurs how many times. But, this is possible only when we know the range of numbers. Even though we know that, it is inefficient in space. So, let's rule out that method. What we have to thus look for, is a way to keep counts / track of a possible majority element run time. How to do this?
What if we consider the smaller part of above given A? We start with count=0. At index_0, we assume 20 is the majority element, thus setting count to 1 and also keep track that '20' is our probable majority number so far. At index_1, we find that the number is not 20 and thus we have lost on score, thus decrementing the count, so not it is 0 again. Here, we are kind of sure that from the elements we have seen so far, each appeared with equal counts and thus, we should look for a new start. So, when count hits 0, we change our probable majority element to the current one and again repeat the process.
With above example, count and probable majority element (pme) go as follows.
A = [20, 4, 4, 7, 4, 16, 20, 4, 0, 4, 4]
count = [ 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1]
pme = [20, 4, 4, 7, 4, 16, 20, 4, 0, 4, 4]
Thus, in O(n) we can find the majority element.
