Puzzles, Maths and Algorithms: Finding Majority Element

Puzzles, Maths and Algorithms: Finding Majority Element
Problem 1: 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 ?

Complexity: Time Complexity = n/2(comparisons), Space Complexity = O(1)

i = 1
while i <= n 
  if A[i] == A[i+1]: return A[i]
  i+= 2

return A[n]

Worst case analysis tells that algorithms would stop when i=n-1 and the number of comparisons done is ~ n/2. This is indeed the best in worst case that we can do.
http://algorithmsforever.blogspot.com/2011/10/majority-element.html

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];

}
Problem 2: 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 the time complexity of the algorithm?

Complexity: Time Complexity=n(comparison), Space Complexity=O(1)

element = A[1]
votes = 1
for i <- 2 to n:
  if A[i] == element
    votes += 1
  else if votes > 0
    votes -= 1
  else:
    element = A[i]
    votes = 1

return element

Problem 3: Now consider that there are k majority elements, i.e., each of the k majority elements appear in the array more than ceil(n/(k+1)) times. How do we find the k majority elements. (Problem 2 is a special case of this problem with k=1).

Complexity: Time Complexity=k*n(comparison), Space Complexity=O(k)  

for i = 1:n
   // update element count in majority array
   for j = 1:k
      if Maj[j] == A[i] 
         Count[j] += 1
         break
      end
   end
   
   // succeeded in above operation (dont go below)
   if k > j
      continue
   end
   
   // Came here, it means that element not in 
   // majority array (put it in an empty slot)
   for j = 1:k
      if Count[j] == 0
         Maj[j] = A[i] 
         Count[j] = 1
         break
      end
   end
   
   // succeeded in above operation (dont go below)
   if k > j
      continue
   end
   
   // Came here, it means that no empty slow 
   // (decrement counts of all majority elements)
   for j = 1:k
      Count[j] -= 1
   end
end  

The algorithm runs in O(nk) time and takes O(k) extra space. It is easy to see that algorithm finds all the k majority elements. This is becase a non-majority element can knock of all the K majority element once. Since there are less than n - k*ceil(n/(k+1)) (< n/(k+1)) non-majority elements, majority elements will survive in the Maj array.
Read full article from Puzzles, Maths and Algorithms: Finding Majority Element