DEV Community

Discussion on: Fun With Linear Time: My Favorite Algorithm

Collapse
 
val_baca profile image
Valentin Baca

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

Collapse
 
healeycodes profile image
Andrew Healey

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 🔍