This can be done in linear time, and a variety of algorithms with this property exist.
Subtle design decisions can make a great difference to their actual performance in practice, especially when used on-the-fly.