Move Zeroes To End - C++ Solution

1. Introduction

The "Move Zeroes To End" problem is a common question in array manipulation. It focuses on rearranging elements in an array to move all zeros to the end while maintaining the relative order of the non-zero elements. This problem tests a developer's ability to efficiently perform in-place array modifications.

Problem

Given an integer array, the task is to move all zeros present in the array to the end. The operation should be done in-place, maintaining the relative order of the non-zero elements. The solution should not use constant space, meaning it should not require additional storage proportional to the size of the input array.

2. Solution Steps

1. Use a pointer (or index) to keep track of the position in the array where the next non-zero element should be placed.

2. Iterate through the array, and when a non-zero element is encountered, place it at the position indicated by the pointer and increment the pointer.

3. After completing the iteration, fill the remaining positions in the array with zeros.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to move all zeros in the array to the end
void moveZeroesToEnd(vector<int>& nums) {
    int position = 0; // Initialize position for next non-zero element

    // Move non-zero elements to the beginning of the array
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] != 0) {
            nums[position++] = nums[i];
        }
    }

    // Fill the remaining array with zeros
    while (position < nums.size()) {
        nums[position++] = 0;
    }
}

int main() {
    vector<int> nums = {6, 0, 8, 2, 3, 0, 4, 0, 1};
    moveZeroesToEnd(nums);

    // Print the modified array
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Output:

6 8 2 3 4 1 0 0 0

Explanation:

The program uses an index position to track where the next non-zero element should be placed. 

As it iterates through the array, non-zero elements are moved to this position, and position is incremented. 

After all non-zero elements are repositioned, the remaining part of the array is filled with zeros. 

This approach efficiently solves the problem in place, maintaining the order of non-zero elements and moving all zeros to the end of the array.