Solving The Move Zeroes Challenge in Python, three approaches

#python #algorithms #codequality

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]

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]

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)

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

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

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)

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.