\(O(1)\) solution I am surprised that the solution posted is \(O(n)\) since \(n\) can be as large as \(10^9\). In coming up with a solution for \(O(1)\) we consider three phases. The first phase accelerates the ‘left hand’ speed until it reaches the terminal speed. If it can’t reach the terminal speed then it just reaches whatever speed it can and terminates. The second phase is like a palindrome stage, where I remove similar increasing speeds from both ends, kind of like climbing up a tall peak from both ends.