A write position
Move the zeros to the end, keeping the order of the rest. About 9 minutes.
A reader and a writer
Imagine tidying a bookshelf by pulling out the empty gaps. One hand reads each slot from left to right. The other hand marks where the next real book should go, and only moves forward when it places one.
That's two positions walking the same array. The reader visits every box. The writer only moves when you keep a value: copy it to the writer's box, then step the writer forward. Zeros are simply skipped.
Read 0: skip it. write stays at 0.
Then fill the gap at the end
When the reader finishes, every kept value sits at the front, in its original order. The writer's position tells you how many there were. Everything from there to the end should become 0.
The writer never gets ahead of the reader, so you never overwrite a box before reading it.
write = 0
for x in nums:
if x != 0:
nums[write] = x
write += 1
for i in range(write, len(nums)):
nums[i] = 0
return numsThe reader has finished copying the non-zero values of 4, 0, 0, 9 to the front. Where is the writer?
- APosition 2
- BPosition 4
- CPosition 1
Show the answer
Position 2. Two values were kept, 4 and 9, so the writer moved twice. Positions 2 and 3 get zeros.
Move the zeros
Move every 0 to the end of the list, keeping the other values in their original order. Change the list in place and return it.
nums = [0, 3, 0, 5, 7] → [3, 5, 7, 0, 0]
0 ≤ n ≤ 1,000,000