DEV Community

Cover image for Solving The Move Zeroes Challenge in Python, three approaches
Nick Langat
Nick Langat

Posted on • Updated on

Solving The Move Zeroes Challenge in Python, three approaches

A while ago, my colleague and I were discussing a very interesting question on data structures and algorithms. This question is provided by LeetCode
Our thoughts were on the different ways we would try to arrive at the solution factoring in all constraints given. To give you a perspective, here is the problem statement:
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
So if we have a list of numbers like:

nums=[8,0,3,5,0,4]
Enter fullscreen mode Exit fullscreen mode

We move all 0's to the end of it while retaining the non-zero numbers such that:

nums=[8,3,5,4,0,0]
Enter fullscreen mode Exit fullscreen mode

The first solution which is not very optimal and would break the in place constraint would be to make a copy of the array and insert non-zero elements by:

nums=[8,0,3,5,0,4]
def move_zeroes():
  zeroes=[]
  non_zeroes=[]
  for i in nums:
    if i ==0:
      zeroes.append(i)
  for i in nums:
    if i !=0:
      non_zeroes.append(i)
  print(non_zeroes + zeroes)
Enter fullscreen mode Exit fullscreen mode

That is a huge chunk so can we tidy it up a lil bit? Of course using list comprehensions such that:

def move_zeroes():
  pri nt([i for i in nums if i !=0]+[i for i in nums if i ==0])
Enter fullscreen mode Exit fullscreen mode

But that wouldn't be the best solution since we need to use constant space and our loop here is disobeying that.
We can build up on what we already have and not use a for loop but swap intermediate elements while checking their values. We can achieve this by using two pointers i and j. i will be our slowest pointer while j the fastest.
Let's construct this logic bit by bit:

def move_zeroes():
  length=len(nums)
  # print(length)
  i=j=0
Enter fullscreen mode Exit fullscreen mode

So we first get the length of our array and store it in a variable. Then we initialize our pointers and assign them to 0 to begin with. After that we can:

def move_zeroes():
  length=len(nums)
  # print(length)
  i=j=0
  while j < length:
    if nums[j]==0:
      j +=1
    else:
      nums[i],nums[j]=nums[j],nums[i]
      j +=1
      i +=1
  print(nums)
Enter fullscreen mode Exit fullscreen mode

So we are going to keep track of j our fastest pointer. As long as it is within the length of our array:
1.We check its value if it is equal to zero. If it is we move the pointer position forward by 1.
2.If j is not zero then we swap j and i then move each of them forwards.

  1. We then return our initial array.

If we run that logic the stats are:
stats
Which is decent if anything is to go by.
Thanks for reading through and see you on the next one.

Top comments (2)

Collapse
 
coullence profile image
Coullence

This is great... I like it when you consider to break down the chunk into smaller readable bits of code.

Collapse
 
nick_langat profile image
Nick Langat

Thanks