Move Zeroes Problem Solved ( C++, Java, Python)

 

There are many questions based on the array asked in technical interviews and students need to have a thick grasp on them. Tt is the most basic data structure that stores a large variable simultaneously. In this article, we will try to solve the Move Zeroes problem using various ways.

What is the Move Zeroes problem?

In the Move Zeroes problem, we are given an array and we have to move all the zeroes to the end of the array, while the non-zero elements should maintain the respective order.

Let’s see an example:

Input: Arr = [ 2, 4, 5, 0, -1, 0, 0, 1, 0]

Output:  Arr = [2, 4, 5, -1, 1, 0, 0, 0]

The most basic approach is to swap the zero with the last non-zero element present in the array. Traverse the whole array and whenever you find the zero, find the first non-zero element present after that zero. Swap the zero with that element till no non-zero is found. Let’s see the example:

The array given to you is:

After the first iteration of the array, we are:

After the second iteration, the array will be:

After the third iteration, our loop will terminate as no more non-zero elements are present after that.

The time complexity of the above approach is O(n*n) where n is the size of the given array. In this approach, we traverse the array once to find all the elements with the value 0. After getting a 0 value element we are finding the non-zero element in the same loop which causes time complexity to O(n*n). The space complexity is O(1) as we are not using any extra space. 

The Extra Space Approach 

In the above approach, we are taking O(n*n) time complexity which is huge. But with The Extra Space approach, we will store each non-zero element in a new array.

Now traverse the new array and update the values at each index with the new array elements. If the new array size is smaller than the size of the old array. Fill the remaining values of the old array with zeros. Let’s examine the approach step by step.

1. First, create a vector that will store the nonzero elements.
2. Now traverse the old array and store nonzero elements in the new array.
3. Now find and update the old array with the new array values. 
4. Fill the remaining values of the old array with the zeroes once the new array is completely traversed.

The time complexity is now just O(n), where n is the size of the array. The space complexity is the same. As we are storing the values of the old array into the new array. In the worst case, all the values may be non-zero which is laid to O(n) space complexity.

Optimized Approach

The best approach to solve the Move Zeroes problem is to create an index that will store the index of the zero element present in the array. If we encounter any non-zero element in the array we will simply swap that with the zero element index and update our index to index+1.

Let’s examine this approach step by step:

1. Create a variable x and initialize it with 0.
2. Iterate over the array, if you encounter any non-zero element swap this element with the element present at index x. Now update the index x to x+1.
3. Repeat the same process for the whole array.

Now is the time to code it practically.

C++ Code

Here is the C++ program to move zeroes to the end of array:

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

int main(){

    vector<int>nums = {0, 1, -1, 0, 2, 3, 0};

    int x = 0;

    for(int i=0; i<nums.size();i++){

        if(nums[i]!=0){

            swap(nums[i], nums[x]);

            x++;

        }

    }

    cout<<"After moving zeroes to the back array will look like "<<endl;

    for(int i=0; i<nums.size();i++){

        cout<<nums[i]<<" ";

    }

    return 0;

}

Java Code

Here is the Java program:

import java.util.*;

public class MoveZeroes {

    public static void main(String[] args) {

        List<Integer> nums = new ArrayList<>(Arrays.asList(0, 1, -1, 0, 2, 3, 0));

        int x = 0;

        for (int i = 0; i < nums.size(); i++) {

            if (nums.get(i) != 0) {

                Collections.swap(nums, i, x);

                x++;

            }

        }

        System.out.println("After moving zeroes to the back array will look like");

        for (int num: nums) {

            System.out.print(num + " ");

        }

    }

}

Python Code

We can also solve the problem with Python:

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

x = 0

for i in range(len(nums)):

    if nums[i] != 0:

        nums[i], nums[x] = nums[x], nums[i]

        x += 1

print("After moving zeroes to the back array will look like")

for num in nums:

    print(num, end=" ")

Output: 

After moving zeroes to the back array will look like
1 -1 2 3 0 0 0

The time complexity of the optimized approach for the Move Zeroes Problem is O(n) as we are just traversing the array once. The space complexity is also reduced to O(1) as we are not using any extra space.

Here is a comparison of all the methods:

Conclusion

In this article, we solved the Move Zeroes problem from the leetcode. We saw that the optimized approach had reduced the time complexity from O(n*n) to O(n) and it has also reduced the space complexity from O(n) to O(1). Some of the other problems you can practice with are finding the degree of an array, finding kth largest element, the Valid Mountain Array problem, etc.