Move Zeroes | LeetCode 283 | Python | Solution

Click here to see the problem details on LeetCode.

Problem Overview

This problem’s difficulty level is easy. The problem description is straightforward. In an integer array, we have to move all 0’s to the end of it. And maintain the relative order of other elements. Suppose we have an array [2, 0, 1] as an input. If we move the zero to the end, the result will be [2, 1, 0]. As in the input array, element 2 comes before 1. So in our final result, we are not allowed to change this order. So [1, 2, 0] is counted as a wrong answer.

One more thing, we don’t need to return anything. All changes we will make on the given array.

Solution One

If we know about the Python list method, the following solution might come to your mind. In my case, this solution came to mind first.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        for i in range(nums.count(0)):
            nums.remove(0)
            nums.append(0)

It’s an easy solution, and it will get accepted.
But this one is inefficient compared to the next one. Because of the time complexity of the remove method is O(n). So the complexity of this solution will be O(n^2).
So let’s get into the next solution.

Solution Two

In this solution, we will declare a variable (z) for tracking 0. This variable initially points to the first element of the given array. Then we will be traversing the given array using a loop. Each time we will check the current element value is 0 or not. If it’s not 0, we will swap the current element value with the nums[z]‘s value (nums[i], nums[z] = nums[z], nums[i]). After that, we will increase the value of the z variable by 1. Otherwise, we will do nothing.

After the loop, all the zero will move to the end.

Let’s see the following solution.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        z = 0
        
        for i in range(len(nums)):
            
            if nums[i] != 0:
                nums[i], nums[z] = nums[z], nums[i]
                z += 1

This solution’s time complexity is O(n).

Suppose the given integer array is [2, 0, 1].

1st iteration
i = 0, z= 0
nums[i] = 2, nums[z] = 2
if 2 != 0
  [2, 0, 1] => [2, 0, 1]
  z(0) += 1

2nd iteration
i = 1, zero = 1
nums[i] = 0, nums[z] = 0
if 0 != 0 => false

3rd iteration
i = 2, zero = 1
nums[i] = 1, nums[z] = 0
if 1 != 0
  [2, 0, 1] => [2, 1, 0]
  z(1) += 1

Loop finished.

Final result = [2, 1, 0]

I hope you got the idea about the problem and the solution.

Tags: ArrayLeetCodeProblem SolvingPython