re: Fun With Linear Time: My Favorite Algorithm VIEW POST


Your code is missing an important element:

"Even when the input sequence has no majority, the algorithm will report one of the sequence elements as its result....This second pass is needed, as it is not possible for a sublinear-space algorithm to determine whether there exists a majority element in a single pass through the input."

Otherwise, [A, B, C] => C


Hi Valentin, a majority element cannot be confirmed with one-pass but if there is a majority element (as per the problem statement) it will be found 🔍

code of conduct - report abuse