Election Computer Science Problem

Problem: There is an election. You are given a stream of votes, in the form of [a, b, a, a, c, b, c, c, a, b, ...]. You do not know ahead of time the number of votes nor the number of contestants. Figure out who wins the election in linear time and constant space without mutating the original input. You may assume that one candidate wins (ends up with more than 50% of the votes).

The key observation here is that, because one contestant claims more than half of the votes, you can pair each vote for the winner with a vote for a loser. In addition, once you come across one of these pairs, you can remove the pair from the stream without affecting the outcome of the election. Also, if you have a pair of losing votes, you can remove those as well from the stream without affecting the election. The only thing you can’t do is remove a pair of votes for the winner. One easy way to enforce this is to only choose pairs of votes for distinct candidates.

Therefore, one algorithm is to successively remove pairs of votes for distinct candidates, until only votes for one candidate are left. A naive implementation of this algorithm requires rewinding the stream. You can do a little better if you assume that the first vote is a vote for the winner. If you increment a counter every time you come across a vote for this contestant, and decrement it every time you come across a vote for any other contestant, when the counter reaches 0 again, you can effectively start the stream anew at this location. This algorithm works even when the first vote is a vote for a loser, because removing pairs of losing votes does not affect the outcome of the election. Eventually, when you reach the end of the stream, whoever has been incrementing your counter has votes leftover, and is therefore the winner.