Move Zeroes
Problem statement
Given a list of integers nums, push every 0 to the end of the list while keeping the relative order of the non-zero values the same. Do it in place — modify the array you were given instead of returning a new one.
This is the same shape as compacting a list of worker slots: keep the busy workers in their original order at the front, and push the idle (zero) ones to the back, without allocating a second list.
Examples
Example 1
Input: nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]
Explanation: The non-zero values 1, 3 and 12 keep their original order and move to the front; the two 0s end up at the back.
Example 2
Input: nums = [0]
Output: [0]
Explanation: A single zero has nowhere to move — the array is already in the required shape.
Hints
Approach
Optimal: Two pointers, in-place swap
Intuition
You don't need a second list to keep the non-zero values in order — you can slide them to the front of the same array as you go. Keep a pointer insertPos marking the next open spot for a non-zero value, starting at 0. Scan the array left to right with a second pointer i. Whenever nums[i] is non-zero, swap it with nums[insertPos] and move insertPos forward. Everything before insertPos is already a non-zero value placed in its original order, so the swap never disturbs what's already there — at worst it swaps a non-zero value with itself.
By the time the scan finishes, every non-zero value has been moved to the front in order, and every zero has been pushed toward the back through the swaps, with no extra memory beyond the two pointers.
Steps
- Set
insertPos = 0. - For each index
ifrom 0 to the end of the array:- If
nums[i] != 0, swapnums[insertPos]andnums[i], then incrementinsertPos.
- If
- When the loop ends, the array is arranged correctly — nothing else to do.
Dry run
nums = [0, 1, 0, 3, 12]
| i | nums[i] | action | insertPos after | array after |
|---|---|---|---|---|
| 0 | 0 | skip | 0 | [0, 1, 0, 3, 12] |
| 1 | 1 | swap(0,1) | 1 | [1, 0, 0, 3, 12] |
| 2 | 0 | skip | 1 | [1, 0, 0, 3, 12] |
| 3 | 3 | swap(1,3) | 2 | [1, 3, 0, 0, 12] |
| 4 | 12 | swap(2,4) | 3 | [1, 3, 12, 0, 0] |
Edge cases: [0] has insertPos staying at 0 the whole loop since the only value is zero, so nothing swaps and the array is unchanged — already correct. An array with no zeros swaps every value with itself, which is harmless and leaves the array unchanged.
Complexity
Time O(n) - the scanning pointer `i` visits every index exactly once, and each swap is O(1) work, so the whole pass is linear
Space O(1) - only the `insertPos` integer is kept; values are swapped within the existing array, so no extra memory grows with the size of the input.
class Solution:
def moveZeroes(self, nums: list[int]) -> None:
insert_pos = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[insert_pos], nums[i] = nums[i], nums[insert_pos]
insert_pos += 1
if __name__ == "__main__":
a = [0, 1, 0, 3, 12]
Solution().moveZeroes(a)
print(a) # [1, 3, 12, 0, 0]
b = [0]
Solution().moveZeroes(b)
print(b) # [0]RecapThe whole problem in a few lines, for the night before
- Spot it: push all zeros to the end in place, keeping the order of the others
- Idea: keep a write pointer; copy each non-zero value to it and move it forward, then fill the rest with zeros (or swap)
- Cost: O(n) time, O(1) space
- Trap: do not build a new array, and do not change the relative order of the non-zero values
Interview follow-ups
The interviewer asks you to minimize the number of writes, not just the number of comparisons — can you do better?
Yes — the current solution writes on every non-zero value it swaps, including harmless self-swaps when
insertPos == i. Skip the swap when the two indices are equal and only actually write wheninsertPos != i; this changes nothing about correctness but cuts wasted writes to zero, which matters more than you'd think when the array lives in slow memory.What if you had to move all zeros to the *front* instead of the end?
Run the same two-pointer scan but shift the write position for non-zero values to fill in from the back of the array instead of the front — scan right to left, and swap each non-zero value into the last open slot, working backward. The core idea (walk once, swap non-zero values into a moving "next open slot" pointer) is unchanged; only the direction flips.
Frequently asked questions
Overwriting nums[insertPos] = nums[i] without saving what was at insertPos first would lose that value if it was itself a non-zero waiting to be moved. Swapping trades the two values instead of discarding one, which is what keeps every value present in the array at every step — nothing is ever deleted, only relocated.
Yes — insertPos only increases when a non-zero value is found, and it increases by exactly 1 each time, while i always increases by 1 every iteration regardless. So insertPos can never get ahead of i, which guarantees the swap always exchanges two values that are still "live" in the scan.
Compacting a list in place while preserving order shows up when you reclaim slots in a fixed-size buffer, pack active connections to the front of a pool, or garbage-collect null entries from a request queue without allocating a new array under memory pressure.
