Move Zeroes — Two-Pointer In-Place Solution

The Problem

Move all zeros in an integer array to the end while keeping the relative order of the non-zero elements. You must do it in place — no copying to a second array. The follow-up asks you to minimize the total number of operations.

The constraint about preserving order rules out a partition-style swap. We need a stable, in-place rearrangement.

Intuition

The naive approach copies non-zero elements into a fresh array, fills with zeros, then copies back. O(n) time but O(n) extra space.

A second naive approach scans the array and, every time it finds a zero, shifts subsequent elements left by one. O(n^2) — too slow.

Use a write pointer. Walk through the array with a read pointer i. Whenever nums[i] is non-zero, write it to position write and increment write. At the end, fill positions write through n-1 with zeros.

A more compact variant swaps nums[i] and nums[write] whenever a non-zero is found. That minimizes writes — only positions that actually need changing get touched. The swap version is what most interviewers prefer because it answers the follow-up.

Explanation with Example

Take nums = [0, 1, 0, 3, 12]. Watch the swap version.

i=0 nums=[0,1,0,3,12]   write=0  (zero, skip)
i=1 nums=[1,0,0,3,12]   write=1  (swap 1 and 0)
i=2 nums=[1,0,0,3,12]   write=1  (zero, skip)
i=3 nums=[1,3,0,0,12]   write=2  (swap 3 and 0)
i=4 nums=[1,3,12,0,0]   write=3  (swap 12 and 0)

Each non-zero gets swapped exactly once, and each zero stays put until a non-zero leapfrogs over it.

Code

def moveZeroes(nums):
    write = 0
    for i in range(len(nums)):
        if nums[i] != 0:
            nums[write], nums[i] = nums[i], nums[write]
            write += 1

class Solution {
    public void moveZeroes(int[] nums) {
        int write = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int tmp = nums[write];
                nums[write] = nums[i];
                nums[i] = tmp;
                write++;
            }
        }
    }
}

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int write = 0;
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (nums[i] != 0) {
                swap(nums[write], nums[i]);
                write++;
            }
        }
    }
};

Edge Cases

An empty array or single-element array is unchanged. An all-zero array is already in the target form: the write pointer never advances. An array with no zeros is unchanged because every swap is a no-op (write and i point to the same index). A single zero gets pushed to the end as expected.

There are no overflow concerns. The algorithm only swaps and compares to zero.

Complexity Analysis

Time is O(n): each index is visited once. Space is O(1) — only two integer pointers.

Number of writes: the swap version writes exactly 2 * (number of non-zeros that are out of place). The two-pass version writes once per non-zero plus once per trailing zero, which is n in the worst case. So the swap version minimizes writes, which matters in scenarios like flash memory or expensive observers.

How to Explain It in an Interview

Say: “I will use a write pointer that always references the next slot a non-zero should land in. As I sweep with a read pointer, every non-zero gets swapped into that slot. Zeros get pushed to the right naturally because later non-zeros swap past them.”

Then write the swap version and trace through a four-element example. Mention the write-count optimization as the answer to the follow-up.

Related Problems

• Remove Element — same write-pointer pattern with a target value.
• Remove Duplicates from Sorted Array — write-pointer plus equality check.
• Sort Colors — Dutch National Flag, three-way partition.
• Merge Sorted Array — pointers from the back.