Move Zeroes

Given an integer list nums, shift every 0 to the end of the list while keeping the non-zero values in the same relative order they started in.

You must rearrange nums in place: do not build and return a new list. The function returns nothing; the judge inspects nums after your function finishes.

Try to keep the number of writes to the list small.

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

Pattern Path · Two Pointers · problem 17 of 169

Start simple

Copy the non-zero values into a new list, pad it with zeroes, and copy it back: O(n) time but O(n) extra space; repeatedly bubbling each zero to the end is O(n²).

The key idea

Use two pointers that move in the same direction. write marks the boundary of the finished prefix, which holds exactly the non-zero values seen so far, in their original order. read scans every element.

When read finds a non-zero value, swap nums[read] with nums[write] and advance write. Everything between write and read is always a zero (those are the zeroes that have been skipped), so the swap moves a non-zero value forward and a zero backward, never disturbing the order of the non-zero values.

When the scan ends, the prefix up to write is all the non-zero values in order and everything after it is zero. Swapping (instead of overwriting and then filling zeroes afterwards) also means a list with no zeroes is never rewritten with different values.

Complexity

• Time: O(n)
• Space: O(1)

Python

class Solution:
    def moveZeroes(self, nums):
        write = 0  # nums[:write] holds the non-zero values found so far
        for read in range(len(nums)):
            if nums[read] != 0:
                nums[write], nums[read] = nums[read], nums[write]
                write += 1

JavaScript

var moveZeroes = function(nums) {
  let write = 0; // nums[0..write) holds the non-zero values found so far
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== 0) {
      [nums[write], nums[read]] = [nums[read], nums[write]];
      write++;
    }
  }
};

What the interviewer is checking

It checks whether you can maintain an invariant with read/write pointers to partition an array in place while preserving relative order.

Mistakes to avoid

• Returning a new list instead of modifying nums.
• Removing zeroes with remove/splice inside a loop, which is O(n²) and easy to get wrong while iterating.
• Using a non-stable partition (swapping from both ends), which scrambles the order of the non-zero values.

Follow-ups to expect

• Can you minimise the total number of writes? (Skip swaps when read equals write.)
• How would you move all values equal to some k? (Same pointer pattern, different test.)
• What if order did not matter? (Swap with the end pointer.)

In real software

Compacting a buffer by pushing deleted or empty slots to the end, as garbage collectors and in-memory tables do, uses this stable in-place partition.

Practice next