Move Zeroes — Solution

Problem

Given an array of integers, rearrange it so all zeros end up at the back while the non-zero elements keep their original relative order. The modification must happen in-place — no returning a new array.

• Input: nums = [0, 1, 0, 3, 12]
• Output: [1, 3, 12, 0, 0]
• Explanation: The non-zeros (1, 3, 12) stay in order at the front; both zeros shift to the back.

An array with no zeros, like [1, 2, 3], should be returned unchanged.

Intuition

Think of a slow "write" pointer that only advances when it places a real value. A fast read pointer sweeps left-to-right handing non-zeros to the write pointer one by one. At the end of the sweep, every index from the write position onward still holds a stale non-zero value — those must be explicitly overwritten with 0. This two-speed approach compacts all non-zeros forward in a single pass without any extra storage.

Approach 1 — Extra Space

Collect all non-zero elements into a separate list, copy them back to the front of nums, then zero out the rest.

1. Scan nums and gather every non-zero element into a temporary list.
2. Write the non-zeros back starting at index 0.
3. Fill every remaining slot with 0.

1def moveZeroes(nums: list[int]) -> None:
2    non_zeros = [x for x in nums if x != 0]
3    for i, val in enumerate(non_zeros):
4        nums[i] = val
5    for i in range(len(non_zeros), len(nums)):
6        nums[i] = 0  # zero out slots that non-zeros vacated

Time: O(n) — two linear passes over the array.
Space: O(n) — the temporary list holds up to n elements.

Approach 2 — In-place Two Pointers

Use a write_pos integer to track where the next non-zero should land. One read pass places every non-zero; a short second pass zeros the tail.

1. Initialize write_pos = 0.
2. Walk through nums; whenever the current element is non-zero, copy it to nums[write_pos] and advance write_pos.
3. After the loop, overwrite every index from write_pos to the end with 0.

1def moveZeroes(nums: list[int]) -> None:
2    write_pos = 0
3    for num in nums:
4        if num != 0:
5            nums[write_pos] = num
6            write_pos += 1
7    while write_pos < len(nums):
8        nums[write_pos] = 0  # zero out slots the non-zeros vacated
9        write_pos += 1

Time: O(n) — one forward pass plus at most n zero-fill writes.
Space: O(1) — all work is done directly in the input array.

Complexity Summary

Common Mistakes

• Forgetting to zero out the tail. After compacting non-zeros forward, the vacated slots still hold their old values. Without explicitly writing 0 from write_pos to the end, you get wrong output like [1, 3, 12, 3, 12] instead of [1, 3, 12, 0, 0].
• Sorting the array. nums.sort() places 0s first (0 is the smallest value), not last, and scrambles the relative order of non-zeros.
• Swapping instead of overwriting, then also needing the tail pass. Swapping nums[write_pos] with the current element is correct, but the value at write_pos is always 0 at that point — a direct overwrite is simpler and avoids the extra swap cost.
• Skipping the in-place requirement. Building a new list and returning it (or assigning nums = new_list) does not modify the original array; the caller's reference still points at the untouched input.
• Off-by-one in the zero-fill loop. Writing while write_pos <= len(nums) instead of < len(nums) causes an index-out-of-bounds on the last iteration.

Related Problems

• Sort Colors — same write-pointer sweep, but partitions an array into three categories instead of two
• Squares of a Sorted Array — two-pointer rearrangement that fills a result array from both ends simultaneously
• Find All Numbers Disappeared in an Array — another in-place array trick that avoids extra space by using the array itself as a marker
• Remove Nth Node From End of List — fast/slow two-pointer idea adapted to a linked list
• Partition List — the same "separate elements into two groups while preserving order" goal, applied to a linked list around a pivot value