Move Zeroes

Given an integer array nums, move all 0's to the end of it while keeping the relative order of the non-zero elements.

You must do this in-place, without making a copy of the array.

Constraints:

• 1 <= nums.length <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

Follow up: Could you minimize the total number of operations?

Brute Force

Collect all the non-zero values in a temporary array, then write them back and fill the rest with zeros.

1. Walk through nums and copy every non-zero value into a temporary array.
2. Write those values back into nums, starting at index 0.
3. Fill the remaining positions with 0.

This works, but it uses extra memory for the temporary array. The problem says we must do it in-place without making a copy, so this approach breaks that rule.

class Solution {
    public:
    void moveZeroes(vector<int>& nums) {
        vector<int> nonZeros;

        for (int value : nums) {
            if (value != 0) {
                nonZeros.push_back(value);
            }
        }

        int index = 0;

        for (int value : nonZeros) {
            nums[index] = value;
            index++;
        }

        while (index < nums.size()) {
            nums[index] = 0;
            index++;
        }
    }
};

• Time: O(n). Two passes over the array.
• Space: O(n). The temporary array can hold every value.

Optimal Approach: Two Pointers with Swap

We keep all non-zero values at the front, in their original order, and let the zeros collect behind them.

We use two pointers:

• insertIndex: the position where the next non-zero value should go. It starts at 0.
• readIndex: the position we are reading now.

Steps:

1. Set insertIndex = 0.
2. Loop readIndex from 0 to the end.
3. If nums[readIndex] is not zero:
   • If readIndex and insertIndex are different, swap nums[readIndex] with nums[insertIndex].
   • Move insertIndex forward by one.
4. If it is zero, do nothing and keep reading.

Everything before insertIndex is non-zero, and everything between insertIndex and readIndex is zero. Swapping moves a non-zero value forward and pushes a zero back.

The check readIndex != insertIndex avoids useless swaps of an element with itself, which helps the follow-up about minimizing operations.

class Solution {
    public:
    void moveZeroes(vector<int>& nums) {
        int insertIndex = 0;

        for (int readIndex = 0; readIndex < nums.size(); readIndex++) {
            if (nums[readIndex] != 0) {
                if (readIndex != insertIndex) {
                    swap(nums[readIndex], nums[insertIndex]);
                }

                insertIndex++;
            }
        }
    }
};

Complexity

How to Explain It in an Interview