Move Zeroes (LeetCode 283)

The problem

You get an integer array nums. Move all the 0s to the end in place, while keeping the non-zero numbers in the same relative order. Don’t make a copy of the array.

Input:  nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

The non-zeros 1, 3, 12 keep their order, and the two zeros end up at the back.

How to think about it

Start with brute force. Build a new list of the non-zeros, then pad it with zeros. That’s O(n) time but O(n) extra space, and the problem forbids the copy. A “bubble each zero to the end” approach stays in place but costs O(n²) swaps.

The key insight: this is “keep the good ones” in disguise. Think of non-zeros as the elements you want to keep in a prefix, in order. It’s the same shape as removing duplicates: one pointer reads every element, another marks where the next keeper goes.

Swapping instead of overwriting finishes the job. If you just copied non-zeros forward, you’d have to fill zeros at the end afterwards. By swapping nums[i] with nums[k], the zero that was sitting at k is moved back to i. So zeros drift to the back as a side effect, in a single pass.

Which pattern is this? Same-direction two pointers (read/write). The tell is “rearrange in place, keep relative order”.

Approach

1. Set k = 0, the slot where the next non-zero belongs.
2. Scan i from left to right.
3. When nums[i] is non-zero, swap nums[i] and nums[k], then increase k.
4. After the scan, nums[:k] holds the non-zeros in order and the rest are zeros.

Solution

def move_zeroes(nums):
    k = 0                                              # next slot for a non-zero
    for i in range(len(nums)):
        if nums[i] != 0:
            nums[k], nums[i] = nums[i], nums[k]; k += 1   # swap keeper forward
    return nums
# move_zeroes([0,1,0,3,12]) -> [1,3,12,0,0]

Dry run

On nums = [0, 1, 0, 3, 12]:

The result is [1, 3, 12, 0, 0].

Complexity

• Time: O(n). One pass, with at most one swap per element.
• Space: O(1). Just the index k; the swaps happen in place.

Edge cases and pitfalls

• No zeros: every element swaps with itself (k == i), so the array is unchanged.
• All zeros: nothing is swapped, k stays 0, and the array is unchanged.
• Empty array: the loop doesn’t run; returns [].
• Sorting is wrong. sort() with a key that pushes zeros back works but is O(n log n), and a plain sort destroys the order of the non-zeros.
• Removing zeros with remove() in a loop is O(n²) and mutates the list while you’re indexing it.

Related problems

• Remove Duplicates from Sorted Array (LeetCode 26): the same read/write template with a different “keep” rule.
• Sort Colors (LeetCode 75): partition into three groups in one pass instead of two.
• Squares of a Sorted Array (LeetCode 977): another two-pointer array rebuild, this time from both ends.