Move Zeros to the end of the list

This coding exercise is part of "30-day-leetcoding-challenge" campaign.

The link to the challenge is here: https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/528/week-1/3286/

The challenge is to shift Zeros to the end of the list, while keeping the relative order of the Non-Zero elements, without using no extra memory. For example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Solution 1: Bubble sort style

Inspired by Bubble sort, we can compare every two neighbours and swap them if first one is Zero. Eventually, at each step zero values shift one step towards the end of the list.

The time complexity is O(N2), but no extra memory is needed.

for i in range(len(nums)):
   for j in range(len(nums)-i-1):
      if nums[j] == 0:
         # swapp zero with the next value
         nums[j] , nums[j+1] = nums[j+1] , nums[j]
        

Solution 2: using two pointers

In this approach, there are two pointers, one pointer holds the location of next Non-zero Element (the slow pointer), and the second pointer searches for Non-zero elements (fast pointer). This solution is optimum, has time complexity of O(N) and space complexity of O(1), no extra space is needed.

  slowP = 0;
  for e in nums:
      if e != 0 :
         nums[slowP] = e
         slowP+=1
        
  #once all non zero elements are moved to top of the array
  # the rest of the array contains Zero(s)
  while slowP < len(nums) :
       nums[slowP] = 0
       slowP+=1

Solution 3: using Python list built in Sort funtion

This solution is not optimum but uses the Python list built in Sort function, which has the time complexity of O(N log N). The code is just one line.

In this code we take the advantage of sort function, which accepts customize sorting function key.

In our case if element is zero, our function evaluates it as True (1), otherwise False (0). Then sort the 1 and 0, which will get us the order we want.

nums.sort( key= lambda x: x==0)