Majority Element

Suppose there is an election to be held, with the following criteria:
1. There are m candidates.
2. There are n voters.
3. A candidate wins if (s)he gets strictly > 50% of the votes.

So, how do you decide if there is a winner? And if there exists one, how do you find him/her?

Sorting

We sort all the votes (in either increasing or decreasing order). Thereafter, we count all the votes for each candidate. If any candidate gets > 50% of the vote, we declare him/her the winner.

The pseudo code looks like:

sort(votes)
n = length(votes)
start_index = 0
end_index = 0
while (end_index <= n):
    while (end_index<n and votes[end_index]==votes[start_index]):
         end_index++
    votes_for_this_candidate = end_index-start_index
    if votes_for_this_candidate > 50% of n:
        declare this_candidate as winner
        break
    else:
        continue

The above takes O(n*log(n)) time. However, it runs in O(n) space (the recursion stack takes O(n) space. Thanks to Piyush Bansal for pointing that out.

Mapping

Another way would be to create a map of each element and its count. The pseudo code would look like this:

map M
n = number_of_votes
for vote in votes:
    if vote present in M.keys:
         M[vote]++
    else:
         insert vote into M with M[vote] = 1
for key in M:
    if M[key] > 50% of n:
         declare key as winner

This runs in O(n) time (insertions and updates in map). However, this takes O(m) space, where m is the number of candidates in the election.

Boyer-Moore Majority Vote Algorithm

This algorithm solves the majority problem in linear time and in constant space.

Idea

Suppose there exists a majority element. We break votes into two sets (mathematical sets), A and B such that A only contains the majority element. In that case, size of A will be greater than size of B (since majority element appears > 50% times).

So it would be possible to map each element of B to a different element in A, and some elements in A would remain unmapped.

Better explained with an example:

Say that number of votes is 21, and majority element is ‘m’. Then, we can definitely say that m occurs > 10 times.

So consider set A consisting only of m’s, and set B consisting of all other elements. Size of A ≥ 11. Size of B ≤ 10.

Hence, each element of B could be mapped to a different m, and we would still be left with some unmapped m .

An O(1) space and O(n) time solution

The above idea can be used as follows:

1. Take an empty stack
2. For each vote, do the following:

• If the stack is empty, add the vote to the stack.
• If the top of stack is same as vote, add the vote to the stack.
• If the top of the stack is different from vote, remove the top of the stack.

The end can have two possibilities:

• The stack is empty → there is no majority element in the array
• The stack is not-empty. If the stack is not empty, it is guaranteed that all elements in the stack will be the same (think why). In this case, the element present in the stack is a candidate for majority element.

Intuition

The above algorithm can be thought of as making pairs of different elements (vote and top of the stack) and removing them. As we saw above, if there is a majority element, it wouldn’t be possible to map all it’s occurrences to a different element. Hence, the elements which are not present in the stack are definitely not majority elements.

Going from a Stack to a simple counter

Pseudo Code

The pseudo code looks like:

candidate_for_majority_element = None
count = 0
#part-1 finding out the candidate
for vote in votes:
    if count==0:  #no candidate for majority element
        candidate_for_majority_element = vote
        count++
    else if vote == candidate_for_majority_element:
         count++
    else
         count--
#part-2 finding if the candidate is indeed a majority element
count = 0
for vote in votes:
    if vote == candidate_for_majority_element:
        count++
if count > 50% of length(votes):
    return candidate_for_majority_element

Follow Up

Given a list of votes, find all candidates who got >33% of the votes. Again, the solution should run in O(n) time and in constant space.