Finding a majority element in one pass
A stream of items is read once, from left to right. Using only a constant number of memory words, find an item that occurs more than times, assuming such an item exists. Then explain how a second pass can check whether a majority exists at all.
History and references
Solved in 1981 by Robert S. Boyer and J Strother Moore.
Boyer and Moore published their algorithm in 1981, and it is a prototypical streaming algorithm. Keep a candidate and a counter that starts at zero. For each item, if the counter is zero, make the item the candidate and set the counter to 1, otherwise add 1 if the item equals the candidate and subtract 1 if it does not. Each decrement cancels one occurrence of some value against one occurrence of a different value, and a value that fills more than half the stream cannot be cancelled completely, so it is the final candidate. If no majority is guaranteed, the final candidate may be wrong, and a second pass that counts its occurrences settles the question.
References
Solutions 0
Sign in or create an account to publish a solution