Time complexity should be O(n+n) = O(n)

[Jaime_Luengo_Rozas]

Since the last loop can potentially run for O(n). Good problem tho.

[henry419]

Your are assuming k <= n which is not necessarily true. O(k) is correct.