LeetCode Solution: Move Zeroes Problem

Hello Everyone!

Hope you are making the best out of this Quarantine period to improve your coding and problem solving skills.

In this post, we are going to discuss the solution and the logic behind the Move Zeroes problem of the 30 Days coding challenge on LeetCode.

So let's get started without any further delay.

Problem Statement:

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

Example:

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

Note that the relative order of the non-zero elements remains unchanged in the input as well as the output array.

Explanation:

Here the problem statement is very much clear but the main thing to focus on is the mentioned hints.

The solution to this problem has to be in-place.

What is an in-place solution?

In-place means we should not be allocating any space for extra array.

Anyways, the solution is stil very easy to crack as we are allowed to modify the existing array.

One of the most common examples of an in-place algorithm is the Heap Sort algorithm.

To develop better understanding on this concept, you can refer to this topic on our site here: https://www.studytonight.com/data-structures/heap-sort

However, as a first step, try coming up with a solution that makes use of additional space. For this problem as well, first apply the idea discussed using an additional array and the in-place solution will pop up eventually.

Logic 1 - Non in-place solution:

This solution is just to develop the required logic to understand the in-place algorithm for this problem.

Steps:

1. A non in-place solution can be making use of an extra array of the size equal to that of the input array.

2. Now use a loop and keep updating the new array with all the non-zero values of the original array in the order, by looping from the first element,

3. One should note that by doing this, you have to only copy the non-zero values to the new array. In case you come across a zero, just ignore it and increment the count of zero by 1.

4. By the end of this loop, you will be left with a new array containing all the non-zero entries of the original input array in the same order.

5. Now the final step will be to just use another loop to fill the remaining elements of this new output array with the zeros. Loop shall be iterated as per the zeroes counted in the above step.

Logic 2 - In-place solution:

This is the required solution as per the rules mentioned along with the problem statement.

Steps:

1. Loop through all the elements of the original input array starting from index 0 to length-1 (last element).

2. Maintain 2 different indices to access the array positions. As per below code, i is used to keep a track of the current loop element and j is used to keep a track of the updated array of non-zero element to be filled. (as it's in-place, we will update the same array)

3. If the current element under consideration is non-zero, then update the value at the j index to this element and update the index j. Not that the index j gets updated only for the non-zero elements whereas the index i gets updated for each of the element of the input array (zero as well as non-zero).

4. Now, after the first 3 steps, our array will be filled with all the non-zero elements in the input array and that too in the same relative order as that in the original array.

5. Now we need to fill the remaining elements of the array with 0 to complete it.

After this, the input array a will itself gets updated to the required output array thereby maintaining the required constraint of keeping the algorithm in-place.

Here is the required in-place program, all together, that solves the above problem. (written in Java)

Code:

class Solution {
    public void moveZeroes(int[] a) {
       
        int i=0,j=0;
        
        // t stores the index of the last element, which will be (number of elements - 1) as array index starts from 0.
        int t=a.length-1;
        while(i<=t)
        {
            if(a[i]!=0)
            {
                //copying only the non-zero elements in the original array itself as need to keep it in-place
                a[j++]=a[i]; 
            }
            i++;
        }
        
        // counting the number of zeroes, which will be equal to the total numbers - the non zero numbers.
        j=t-j+1;
        

        //filling the remaining array with the zeros starting from end.
        while(j!=0)
        {
            a[t--]=0;
            j--;
        }
    }     
}

We hope that this step by step explanation to handle each of the possible cases, might have helped you to understand the entire solution to the mentioned problem.

In case of any query, you can reach out to us via Email or can directly post your queries in the comments section down below.

Happy Quarantine : )

You may also like:

• LeetCode Solution - First Bad Version Problem

• LeetCode Solution: Maximum Subarray Problem

• LeetCode Solution: Best Time to Buy and Sell Stock Problem

• LeetCode Solution - Jewels and Stones Problem