Comment by jose_zap

Interestingly, the naive solution presented in this article is O(n) thanks to laziness.