How do you move all the zeroes to the end of an array while preserving the order of the non-zero elements?
You use a write position for the next value that should stay, and you fill the rest of the list with zeroes at the end.
def move_zeroes(nums):
write = 0
for read, value in enumerate(nums):
if value != 0:
nums[write] = value
write += 1
# Everything from here to the end is a zero.
for index in range(write, len(nums)):
nums[index] = 0
return nums
So how does it work? You walk through the list, and every time you find a value that is not zero, you write it at the write position and move the write position along. The values that are not zero are copied over the front of the list in the order they were in, and the write position ends up pointing at the first place that is left over. Then you fill that whole tail with zeroes.
And why does the order survive? Because you only ever write a value to a place that is at or behind where you are reading from. The write position never gets ahead of the read position, so the values that are copied across are always in the order that they were found.
So it is O of n for the time, because you walk through the list twice, and O of 1 for the space, because you never make a second list.
The next question in this topic looks at the shorter version that most people write first.