Add the O(n) space solution and refactor the loop