Majority element

This is a classical problem, quite frequently asked in interviews. Given an array find the majority element. How about a stream?

Solution

There is a trivial O(nlogn) solution based on sorting and counting, but you are not using the majority propriety.

There is another solution based on hashing, but you are not using the majority propriety and this will not work on streams because you cannot bound the hash table.

The majority element will appear by definition on more than 50% of elements. So you can maintain a variable with the current element and another variable with the current counting. When you see the same element you increment, when you see another element you decrement, when you reach zero then you change the current element. In this way, if there is a majority element you will identify it in the current element variable.

What happen if there is no majority element? will you have a false positive?

How to adapt the above principle to a stream?