O(n) time complexity, O(1) memory complexity, the basic idea fits in 15 lines of code (maybe even 10)...