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).