Move Zeroes
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Push all zeros to the end of the list while keeping the order of the other numbers, working in place.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Where should the next non-zero number go?
- Hint 2Keep a marker for the next free front slot and move every non-zero there.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A bus with some empty seats scattered between passengers. The conductor says: "Everyone move forward and fill the front seats, keeping your order." Passengers shuffle forward one by one, and all the empty seats naturally end up at the back.
- The obvious way
Copy the non-zeros into a new list and then append zeros: needs a whole extra list.
- The key insight
Keep a marker "next front slot". Scan the list; every time you meet a non-zero, swap it into the front slot and move the marker one step. Everything before the marker is always the non-zeros in their original order, and the zeros drift to the back.
- The algorithm
- Marker for the next front slot starts at the first position.
- Walk through the list. Zero? Skip it.
- Non-zero? Swap it with the slot at the marker, then move the marker one step.
- When the walk ends, the list is rearranged.
Watch it run
Examplenumbers = [0, 1, 0, 3, 12]
Look at 0: a zero, skip. The marker stays at the first slot.
[0, 1, 0, 3, 12] marker at slot 1
Where people slip
- When the marker and the reader are on the same slot the swap swaps an item with itself, which is harmless.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def move_zeroes(nums):
front = 0 # next free slot at the front
for position in range(len(nums)):
if nums[position] != 0:
nums[front], nums[position] = nums[position], nums[front]
front += 1Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.