the space complexity of first solution is wrong.