Finding Majority Element

Jargon: Majority Element is an element of an array that occurs more than half the number of times in the array. Also, [x] means smallest integer greater than x.

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)

Solution: show

We will use pigeonhole principle to make our clever observations. There can be a maximum of [n/2]-1 elements that are distinct, remaining [n/2] element have to be same (as majority element exists in the array). We can consider that the [n/2]-1 distinct elements to be laid out and the space between two laid out elements to be a basket of infinite size. So we will have [n/2] baskets. If we try to distribute [n/2] majority element to these baskets, then in only one permutation will each basket get one element. Otherwise, some baskets would get more than one element and some baskets would remain empty.

Using this observation, we can claim that to find majority element we need to check adjacent elements for equality or two hop neighbor (adjacent to neighbor) for equality. That requires two comparison per element and the algorithm would look like this:

for i <- 1 to n-2
  if A[i] == A[i+1] or A[i] == A[i+2]
    return A[i]

A quick observation tells that this algorithm's for loop would stop when i=[3n/4]+1 even in worst case and the number of comparisons done will be ~ 3n/2. Now, we can make another clever observation that is, if we do not find two adjacent elements to be equal after complete scanning of array, then first element has to be majority element by pigeonhole principle.

for i <- 1 to n-1
  if A[i] == A[i+1]
    return A[i]
return A[1]

In Worst case this algorithms stops at i=n+1 and the number of comparisons done is = n-1. Even though this looks better than the first solution but it could be worse in practice. On a highly pipelined architecture with branch prediction, first one is much better than the second one, even though it does more comparisons per loop. So testing for large array sizes with random shuffling of elements will give clear insight into which algorithm is faster. Now an extremely clever solution which is based on observation that if we pair array elements and strike out a pair if its both the elements are distinct or else return the pair element as majority element. If all pair are striked out then what ever element is left has to be majority element.

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.

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)

Solution: show

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. This algorithm implements the above idea.

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

This algorithm does n-1 comparisons. The comparisons such as votes > 0 don't count as they are integer variable comparison.

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)  

Solution: show

Algorithm uses the same intuition as that presented for problem 2. But instead of one counter, we keep k counters. Each counter is initialized with a unique element from the array and we maintain count of how many times that element has been seen so far. Now for a new element x, if it matches an element in the counter then its count is incremented by 1. If the counter of an element is 0 then the x replaces that element and its count is set to 1. If x doesnt match any element on the counter, and all elements have count > 0, then all counters are decremented by 1. Then we move to next element. Following code implements this logic.

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.

Airplane Seating Problem

100 passengers are boarding an airplane with 100 seats. Everyone has a ticket with his seat number. These 100 passengers boards the airplane in order. However, the first passenger lost his ticket so he just take a random seat. For any subsequent passenger, he either sits on his own seat or, if the seat is taken, he takes a random empty seat. What's the probability that the last passenger would sit on his own seat?

Answer: 1/2

Solution:
When 100th passenger arrives, only seat 1 or 100 is vacant (rest all must be non-empty). To see this, let seat 50 is vacant. Since passenger 50 came before passenger 100, he would sit in his seat only. Hence seat 50 cannot be vacant. So all permutations of the seating arrangement would result in last person sitting in either seat 1 or seat 100. Both the options are equi-likely.

Tip: Its wiser to solve problems like these for small values and then try to generalize. For e.g. let there be three passengers p1, p2, p3. p1 can sit in seat 1 with prob=1/3. In this case p3 sites in seat 3. p1 can sit in seat 2 with probability = 1/3, p2 can sit in either seat 1 or 3 (with prob=1/2). so p3 gets to sit in his seat with probability = 1/3 * 1/2 = 1/6. p1 can sit in seat 3 with probability 1/3. In this case p3 can sit in seat 3 with probability = 0. So the total probability for p3 to sit in his seat = 1/3 + 1/6 + 0 = 1/2

Tic Tac Toe

Two players are playing a game and take alternating turns. There are 9 cards on the table with numbers from 1 to 9. On each turn, a player picks one card from the table. The first player to have 3 cards that total a sum of 15 wins. If no one can after all cards are distributed, then it's a draw. Can you tell who wins, assume both players are highly and equally intelligent and what is the winning strategy ?
Source: Petr Mitrichev's Blog

Answer: Draw

Solution:
If player 1 picks any card except for 5 then there are three ways he can pick second card in order to total 15. Player 2 will block one way in his following turn. Leaving two options for player 1. For any way that player 1 chooses, he has just one way now to total 15. Player 2 will block that way. Player 2 has blocked all ways of player 1 so far. But in the two moves so far player 2 has one way to reach 15. Player 1's next turn can block that. But, This analysis is hard to follow and unclear to see for all the possible combination.

This problem can be modeled in form of tic-tac-toe by constructing a 3 x 3 magic square, as follows:

4  9  2
3  5  7
8  1  6

Now all rows, diagonals, columns sum to 15. So the problem is reducible to playing a tic-tac-toe. Its easy to see that if two players are highly and equally intelligent then the game would result in a draw.