Beware of using extra space


#1

don’t use extra space unless you want to waste your time debugging.
Same solution worked without O(n) extra space.