Hacker News Reader

That reminds me of my favorite algorithm, which can find the majority element in a list with any number of distinct entries while using O(N) time and O(1) space (provided a majority element exists). I sometimes pose deriving this algorithm as a puzzle for people, no one has ever solved it (nor could I).

https://en.m.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority...

View on HN

What's great about that is that the assumption (or O(n) check) that the majority exists is incredibly powerful, enabling the algorithm, which is nearly the dumbest possible algorithm, to work.

The one flaw in the magic is that "2nd pass to verify" is a significant cost, transforming the algorithm from online streaming O(1) space to O(n) collection-storage space.

Ah shoot I never thought of that. I wonder if there’s a sneaky way around it? You’re right, that definitely impacts the utility of the algorithm.

That is really cool

Reply on news.ycombinator.com