Move Zeros to End

Given an integer array nums, move all the 0's to the end of the array. The relative order of the other elements must remain the same.

This must be done in place, without making a copy of the array.

Brute Force#

Collect all non-zero elements into a temporary array, then write them back to the front of nums, filling the remaining positions with zeros. This correctly preserves relative order and handles the in-place constraint via the second write pass, but requires O(n) extra memory for the temporary array and two full passes over the data.

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();

        vector<int> temp;

        for (int i = 0; i < n; i++) {
            if (nums[i] != 0) {
                temp.push_back(nums[i]);
            }
        }

        int nz = temp.size();

        for (int i = 0; i < n; i++) {
            if(i<nz)
                nums[i] = temp[i];
            else
                nums[i] = 0;
        }

    }
};

Time Complexity: O(2*n)

Space Complexity: O(1)

Optimal Approach: Two pointer#

Maintain a slow pointer j that always points to the position where the next non-zero element should land, starting at 0. The fast pointer i scans the entire array; whenever it finds a non-zero element, it swaps nums[i] with nums[j] and advances j. Because j only moves on a swap, zeros naturally get pushed to the right as non-zeros bubble left. This runs in a single pass with O(1) extra space, strictly better than the brute-force approach.

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

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

Time Complexity: O(n)

Space Complexity: O(1)