Problem Statement

Given an array of integers, the task is to move all zeroes to the end of the array while maintaining the relative order of non-zero elements.

LeetCode:

• https://leetcode.com/problems/move-zeroes/description/

Constraints:

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

Examples

Example 1:

Input: arr[] = {1, 2, 0, 0, 5, 7}
Output: [1, 2, 5, 7, 0, 0]

Explanation: Both the zeroes are moved to the end and the order of the other elements stay the same.

Example 2:

Input: arr[] = {0, 0, 0, 1, -7}
Output: [1, -7, 0, 0, 0]

Explanation: All the three zeroes moved to the end of the array and the order of the other elements is maintained.

Different Approaches

1️⃣ Brute Force with Extra Space

Intuition:

To ideate a solution for the problem, store the non-zero numbers separately and then place those elements back into the original array. This ensures that all the non-zero numbers are kept at the front of the array. Lastly, fill the remaining positions in the array with zeros.

Approach:

1. Declare a temporary array to store all the non-zero elements. Traverse the original array and copy all non-zero elements to the temporary array.
2. Overwrite the original array's starting positions with the elements from the temporary array.
3. Fill the remaining positions in the original array with zeros.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to move zeroes to the end
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();

        /*Create a temporary array to 
         store non-zero elements*/
        vector<int> temp;

        for (int i = 0; i < n; i++) {
            // Copy non-zero elements to temp
            if (nums[i] != 0) {
                temp.push_back(nums[i]);
            }
        }

        // Number of non-zero elements
        int nz = temp.size();

        for (int i = 0; i < nz; i++) {
            // Copy non-zero elements back to nums
            nums[i] = temp[i];
        }

        for (int i = nz; i < n; i++) {
            // Fill the rest with zeroes
            nums[i] = 0;
        }

    }
};

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

    //Create an instance of Solution class
    Solution sol;

    sol.moveZeroes(nums);

    cout << "Array after moving zeroes: ";
    // Print the modified array
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }

    return 0;
}

Complexity Analysis:

• Time Complexity:O(2*N), O(N) for copying non-zero elements from the original to the temporary array. O(X) for again copying it back from the temporary to the original array. O(N-X) for filling zeros in the original array. Here N is the size of the array and X is the number of non-zero elements.
• Space Complexity:O(N), for using a temporary array to solve this problem and the maximum size of the array can be N in the worst case.

2️⃣ Naive Approach (Brute Force) Without Extra Space

Algorithm:

• Iterate through the array.
• For each non-zero element encountered, swap it with the first element found after it.
• Repeat until all non-zero elements are moved to their correct positions.

Code:

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

void moveZeroes(vector<int>& nums) {
    int X = 0;
    // Count non-zero elements
    for (int num : nums) {
        if (num != 0) {
            nums[X++] = num;
        }
    }
    // Fill remaining positions with zeroes
    while (X < nums.size()) {
        nums[X++] = 0;
    }
}

int main() {
    vector<int> nums = {0, 3, 0, 4, 2, 0, 8, 0};
    moveZeroes(nums);
    cout << "Array after moving zeroes to the end: ";
    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}

// Output
Array after moving zeroes to the end: 3 4 2 8 0 0 0 0 

Complexity Analysis:

• Time Complexity: The time complexity of it is O(N), where N is the number of elements in the array.
• Space Complexity: The space complexity is O(1) indicating constant space usage.

3️⃣ Optimal Approach (Using 2 pointers)

We can optimize the approach using 2 pointers. First pointer will point to the first 0 in the array and the another will point to the next index.

Algorithm:

• We use two pointers, left and right.
• The left pointer is responsible for placing all non-zero elements at their correct positions.
• The right pointer iterates through the array.
• We iterate through the array with the right pointer. When encountering non-zero element, we copy it to the position indicated by the left pointer and increment left.
• After iterating through the array, all non-zero elements are moved to the beginning of the array.

Code:

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

void moveZeroes(vector<int>& nums) {
    int left = 0; // Pointer to track the position to place the next non-zero element
    int right = 0; // Pointer to iterate through the array

    // Move non-zero elements to the beginning of the array
    while (right < nums.size()) {
        if (nums[right] != 0) {
            nums[left++] = nums[right];
        }
        right++;
    }

    // Fill the remaining positions with zeroes
    while (left < nums.size()) {
        nums[left++] = 0;
    }
}

int main() {
    vector<int> nums = {0, 3, 0, 4, 2, 0, 8, 0};
    moveZeroes(nums);
    cout << "Array after moving zeroes to the end: ";
    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        // Pointer to track the position where the next non-zero element should go
        int zero = 0;

        // Traverse the array
        for (int i = 0; i < nums.size(); i++) {

            // If the current element is non-zero
            if (nums[i] != 0) {
                // Swap it with the element at index `zero`
                // This pushes non-zero elements to the front
                swap(nums[i], nums[zero]);

                // Move the `zero` pointer forward
                // (it only increases when a non-zero is placed)
                zero++;
            }
        }
    }
};

Complexity Analysis:

• Time Complexity:O(N), where N is the number of elements in the array.
• Space Complexity:O(1)