Move Zeroes

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements. Modify the array in-place with O(1) extra memory.

Note that you must do this in-place without making a copy of the array. Minimize the total number of operations.

Sample Input and Expected Output:

Input:

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

Output:

Modified array: [1, 3, 12, 0, 0]

Input:

nums = [0, 0, 1, 0, 0, 2, 3]

Output:

Modified array: [1, 2, 3, 0, 0, 0, 0]

Move Zeroes Solution in C++:

The idea is to use a two-pointer approach. We use one pointer (i) to iterate through the array and another pointer (j) to keep track of the position where we need to insert non-zero elements. When we encounter a non-zero element at position i, we place it at the position pointed by j and increment both i and j. After we have moved all non-zero elements to the front, we fill the rest of the array with zeroes.

#include <iostream>
#include <vector>

void moveZeroes(std::vector<int>& nums) {
    int j = 0; // Pointer to track the position to insert non-zero elements.

    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] != 0) {
            nums[j] = nums[i]; // Place the non-zero element at the new position.
            j++; // Move j to the next position.
        }
    }

    // Fill the rest of the array with zeroes.
    while (j < nums.size()) {
        nums[j] = 0;
        j++;
    }
}

int main() {
    std::vector<int> nums1 = {0, 1, 0, 3, 12};
    std::vector<int> nums2 = {0, 0, 1, 0, 0, 2, 3};

    moveZeroes(nums1);
    moveZeroes(nums2);

    std::cout << "Modified array: [";
    for (int num : nums1) {
        std::cout << num << " ";
    }
    std::cout << "]" << std::endl;

    std::cout << "Modified array: [";
    for (int num : nums2) {
        std::cout << num << " ";
    }
    std::cout << "]" << std::endl;

    return 0;
}

Time Complexity and Space Complexity:

The time complexity of the solution is O(n), where n is the size of the input vector nums. This is because we use a two-pointer approach that traverses the array once.

The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array. The moving of zeroes is performed in-place, modifying the original array.