30 Day LeetCoding Challenge (Day 4)

Hope you’re having a great day, in case you’re new to this post, and looking for some good editorials on the ongoing LeetCode challenge, here are the editorials for day 1 and day 2.

Note: I haven't posted solutions for the third problem as it is a very common interview question that I believe most people have encountered in their programming coursework. Please let me know in the comments if I should post an editorial for the same.

Leetcode has released its fourth problem for the week. Let’s get cracking.

MOVE ZEROES

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:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

Intuition

Now, as simple as this problem sounds, we must try to do this problem in-place, which means that we are not allowed to create a new array or use any other Data Structure than the one used in the problem statement.

So how do we tackle this problem?

Idea: Let's break down the intuition into a couple of understandable steps.

While we loop through the entire array of numbers,

• If the number is zero, let's initialize a variable count and keep incrementing it by 1.
• If the number is non-zero, let's replace that number with the first(second, third and so on, i.e. pos-th) element of the array and keep incrementing its position by 1.

Once this set of operations is complete, we notice that all the non-zero elements have been shifted to the start of the array, keeping the order of appearance intact.

Let's do a small example

Input: [0,1,0,3,12] 
Lets initialize 
count=0 (keep count of zeroes encountered)
pos=0 (to move elements to the beginning of the array in order)
Lets loop through the array(A) now
i=0, count=1, pos=0    [0,1,0,3,12]
i=1, count=1, pos=1    [1,1,0,3,12] 
.. here we replace A[pos] (pos = 0, here) with A[i] and increment pos by 1, thats why pos = 1.
Now that we've got the gist, lets complete the loop.

i=2, count=2, pos=1    [1,1,0,3,12]
i=3, count=2, pos=2    [1,3,0,3,12]
i=4, count=2, pos=3    [1,3,12,3,12]
Now that all elements have been moved to the start in order, we can run a loop from i=pos till the length of the array and replace all elements with zero, to give us the solution.

Solution

class Solution {
    public void moveZeroes(int[] nums) {
        int pos=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0){
                nums[pos]=nums[i];
                pos++;
            }
        }
        for(int i=pos;i<nums.length;i++)
            nums[i]=0;
    }
}

Let's submit it and see what Leetcode has to say about it.

Voila, accepted.

Lesson Learned: This is a constant space and linear time solution.

Please let me know if I should post an editorial for day 3 as well.

Happy Coding :D