Move Zeroes easy

Problem Statement

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

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

Example 1:

Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0]

Example 2:

Input: nums = [0] Output: [0]

Steps:

1. Two Pointers: We use two pointers, nonZeroIndex and currentIndex. nonZeroIndex tracks the index where the next non-zero element should be placed, while currentIndex iterates through the array.

2. Iteration: We iterate through the array using currentIndex.

3. Non-Zero Element: If nums[currentIndex] is not zero, we swap it with the element at nonZeroIndex. This effectively moves the non-zero element to its correct position. We then increment nonZeroIndex.

4. Zero Element: If nums[currentIndex] is zero, we do nothing; we simply let the zero remain in its current position.

Explanation:

The algorithm cleverly uses the nonZeroIndex to keep track of where the next non-zero number should be. By swapping, we ensure that all non-zero elements are placed before the zeros. The zeros remain in their original relative order since we don't touch them when nums[currentIndex] is zero. The remaining elements at the end of the array will automatically be zeros after this process.

Code:

#include <vector>

void moveZeroes(std::vector<int>& nums) {
    int nonZeroIndex = 0; // Index to place the next non-zero element

    for (int currentIndex = 0; currentIndex < nums.size(); currentIndex++) {
        if (nums[currentIndex] != 0) {
            // Swap non-zero element with the element at nonZeroIndex
            std::swap(nums[currentIndex], nums[nonZeroIndex]);
            nonZeroIndex++; // Move nonZeroIndex to the next position
        }
    }
}

Complexity:

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
• Space Complexity: O(1). We use only a constant amount of extra space (the two pointers).