Majority Element

Majority Element is an element of an array that occurs more than half the number of times in the array.

Easy Problem:
Assume that an integer array A[1..n] has a majority element and elements other than majority element are distinct. How to find majority element. What's the space and time complexity of the algorithm ?

Hard Problem:
Assume that an integer array A[1..n] has a majority element and elements other than majority element need NOT be distinct. How to find majority element. What's the space and time complexity of the algorithm ?

Both easy and hard may be solved using the following solution in ~(n-1) comparisons.

Solution (HARD) :
This algorithm uses an observation that if we consider our array to be list of voters and array value is the candidate to whom they are voting, then majority element is the winning candidate.
Additionally, if all other candidates are merged to form one candidate then still it will fail to defeat the majority element candidate (hence the name majority element).
So we can think of it this way. Assuming a negative vote decrease the count of majority element then still the count of majority element would be atleast 1.

int majority_hard(int[] input, int n){

int element = input[0];
int votes = 1;

for(int i=1; i<n; i++){

if(input[i] == element)

votes++;

else if(votes > 0)

votes--;

else {

element = input[i];
votes = 1;

}

}
return element;

}

However, the easy problem may be solved using ~n/2 comparisons using the pigeon hole principle :

Solution (EASY) :
If the total size N is even then, the majority element must duplicate in consecutive positions in some pairs of positions. If N is odd, then it must either duplicate in consecutive positions or must be the last element.

int majority_easy(int[] input, int n){

for(int i=0; i<N; i+=2){

if(input[i] == input[i+1])

return input[i];

}
return input[N];

}

Complexity :

• Time : O(N)
• Space : O(1)