4 ms·
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
by jdhwosnhw 2y ago
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_vote_algorithm https://en.m.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority...
- barapa 2y agoThat is really cool
- lupire 2y agoWhat'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.
- jdhwosnhw 2y agoAh 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.