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 dumb

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.