Day-3 Move Zeroes

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:

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

This question was published on Leetcode's ongoing 30 days challenge. The date the question was published was 4th April 2020.

Initial Approach

1. Iterate over the list.
2. If the element is 0. Find the index of the element. Use pop, give index as a parameter.
3. In a new list keep appending the popped out elements (zero's).
4. After iteration of the list is complete. Using extend add the zero's of the new list to the end of the original list.

Problem with this initial approach

1. While iterating over the list. If you keep popping the elements out. The index of the elements in the original list will keep changing. Resulting in unexpected outputs.
2. The solution wasn't using moving the zeroes in place. A new list was getting created.

Solution Approach 2

1. Count the total number of zero's in the given list.
2. Initialize a variable named as counter. Keep incrementing this after removing zeros from the original list.
3. Once the zero is removed from the original list. Append the zero again in the original list. (This way zeroes will be at the end of the list).
4. When the value of the counter is equal to the value of count. Break the loop.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        L1 = []
        count = nums.count(0)
        counter = 0
        for x in nums:
            if x==0:
                nums.remove(x)
                nums.append(x)
                counter += 1
            if counter == count:
               break

Above solution is in-place solution. No new list is getting created.
In case you have a more optimized approach. You can comment and discuss it.

Ps: Just please don't show the code directly.

Learnings

1. Don't pop the elements based on the index while iterating over the list.
2. Creating a new list means a new object is getting creating in memory which has a different memory reference id. As the solution is in-place. We are optimizing memory.
3. The time complexity of append is 0(1) while the time complexity of remove is 0(n).

Comments

[Martin Uribe]

Nice article.

I would initialize a counter to 0. Then in a while loop, inside a try/except block do a remove(0) followed by an increment to the counter. In the except I would capture the ValueError and use it to break out of the loop. Finally I would extend the list by [0] multiplied by the value of the counter.

Hope that made sense.

I should start doing some of these but I don’t really like timed challenges...

[Mridu Bhatnagar]

Thank you, Martin.

That's a good approach as well. It looks similar to the initial approach I mentioned. However, [0] multiplied by the value of the counter would create a new list and then you are extending the list. So, the solution would not remain in-place solution. I liked capturing the ValueError approach.

Same here, I don't enjoy time challenges. Also, you can do these at your own pace. I don't do these with time. The place I feel these problems help is in understanding when to use and what to use.

Like through the initial approach I learned why index, pop would not work here, thought in the direction of in-place approach, remove, count, etc ... also have their time complexity to be O(n). So, the time complexity overall turns out to be O(n^2) likewise more similar learnings.

[Martin Uribe]

Extending nums doesn't really create a new list. If you check its id before and after they are still the same. Regardless, that portion of the code could be changed to:

#nums.extend([0] * count)
for _ in range(count):
    nums.insert(len(nums), 0)

And still accomplish the same and be just as fast.

~$: python move-zeroes.py
   mridu: 0.0000188351
clamytoe: 0.0000166893
 striker: 0.0000388622

I still have a lot to learn about big O notation myself. I'm not a professional coder so finding the time to learn takes a lot of effort. Also, not having a use/case for things makes it that much harder to stay focused on certain subjects.

Once again, I'm really impressed with all that you've been doing. It's very inspirational and motivates me to get my butt in gear!

[Mridu Bhatnagar]

I am an absolute beginner in this time complexity thing as well. What I meant by extra memory was. When you do

nums.extend([0] * count)

[0]*count would result in [0, 0, 0]. And this list with [0, 0, 0] will have a different memory id then your nums list.

That try expect thing is really nice. I recently read about it in some blog as well. That this is a good way to do.