Program to Move All Zeroes to the End of Array.

Given an integer array arr[] of size n, the task is to move all zeroes (0's) to the end of the array while maintaining the relative order of non-zero elements.

Example:

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

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

There are multiple approaches to solving this problem. Let's discuss each approach one by one from brute force to optimized one.

Approach 1: Brute Force Approach.

This is a basic approach in which we are going to traverse the complete array to store all non-zero elements in the front of the new array and add the required number of zeroes at the end. Below are the steps to follow:

Create a new array.
Iterate through the original array.
For each non-zero element, add it to the new array.
After completing the iteration, add the required number of zeros to the new array.
The new array will now have all non-zero elements followed by zeros.

Below is the C++ code implementation for the above approach:

//C++ code to move all zeroes at the end of array
#include <bits/stdc++.h>
using namespace std;

vector<int> moveZeroesBruteForce(vector<int>& arr) {
    vector<int> result;

    for (int i : arr) {
        if (i != 0) {
            result.push_back(i);
        }
    }
    //count of 0's present in the array
    int numberOfZeroes = arr.size() - result.size();
    result.insert(result.end(), numberOfZeroes, 0);

    return result;
}

int main(){
    vector<int> arr = {0, 1, 0, 3, 4, 0, 0, 8};

    vector<int> ans = moveZeroesBruteForce(arr);

    for(int i = 0; i < ans.size(); i++){
        cout << ans[i] <<" ";
    }

    return 0;
}

Output:

1 3 4 8 0 0 0 0

Time Complexity: O(n) where n is the number of elements present in the array.

Space Complexity: O(n) where n is the number of elements present in the array.

Approach 2: Optimized Approach.

This is an in-place approach in which we are not going to use any extra space to move all 0s to the end of the array. Below are the steps to follow:

Initialize a variable to keep track of the position to overwrite.
Iterate through the array.
For each non-zero element, overwrite the next position with the current element.
After completing the iteration, fill the remaining positions with zeros.
The array will now have all non-zero elements followed by zeros.

Below is the C++ code implementation for the above approach:

//C++ code to move all zeroes at the end of array
//In-place approach
#include <bits/stdc++.h>
using namespace std;

vector<int> moveZeroesOptimized(vector<int>& arr) {
    int writeIndex = 0; // Position to overwrite

    for (int i : arr) {
        if (i != 0) {
            arr[writeIndex++] = i;
        }
    }

    // Fill the remaining positions with zeros
    while (writeIndex < arr.size()) {
        arr[writeIndex++] = 0;
    }

    return arr;
}

int main(){
    vector<int> arr = {0, 1, 0, 3, 4, 0, 0, 8};

    vector<int> ans = moveZeroesOptimized(arr);

    for(int i = 0; i < ans.size(); i++){
        cout << ans[i] <<" ";
    }

    return 0;
}

Output:

1 3 4 8 0 0 0 0

Time Complexity: O(n) where n is the number of elements present in the array.

Space Complexity: O(1) as no extra space is required to solve the problem using this approach.

Approach 3: Two Pointer Approach.

In this approach, we use two pointers, one to iterate through the array and the next the keep track of position for non-zero values. Below are the steps that need to be followed:

Use two pointers - one to iterate through the array and another to keep track of the position to overwrite.
Iterate through the array.
For each non-zero element, swap it with the element at the position to overwrite.
After completing the iteration, the array will have all non-zero elements followed by zeros.

Below is the C++ code implementation for the above approach:

//C++ code to move all zeroes at the end of array
//In-place two pointer approach
#include <bits/stdc++.h>
using namespace std;

vector<int> moveZeroesTwoPointer(vector<int>& arr) {
    int writeIndex = 0; // Position to overwrite

    for (int i = 0; i < arr.size(); ++i) {
        if (arr[i] != 0) {
            std::swap(arr[writeIndex++], arr[i]);
        }
    }

    return arr;
}

int main(){
    vector<int> arr = {0, 1, 0, 3, 4, 0, 0, 8};

    vector<int> ans = moveZeroesTwoPointer(arr);

    for(int i = 0; i < ans.size(); i++){
        cout << ans[i] <<" ";
    }

    return 0;
}

Output:

1 3 4 8 0 0 0 0

Time Complexity: O(n) where n is the number of elements present in the array.

Space Complexity: O(1) as no extra space is required to solve the problem using this approach.

I hope you understood all three approaches to solving this problem of moving 0s to the end of the given array.

Program to Move All Zeroes to the End of Array.

Approach 1: Brute Force Approach.

Approach 2: Optimized Approach.

Approach 3: Two Pointer Approach.

No comments:

Post a Comment