# move zeroes to end

🏠

Another classic problem. And another one where i saw sacriligiously long solutions.

If a list, e.g

1 A = [1,3,6,5,4,0,6,0,7,0,5,3,0,6,4,0,2]


How would you move all the zeroes to the end of the list?

1 A = [1,3,6,5,4,6,7,5,3,6,4,2,0,0,0,0,0]


## Using Sort

By far the simplest solution is to use sort.

1 def moveZerosToEnd(arr):
2   return sorted(arr, key=lambda x: int(x == 0))


This works because the key to our call to sortedmakes the sorting do one thing only mark zeroes with a 1, meaning shifting the values to the right, and marking everything else with a 0 which keeps them in the same position.

The default sort / sorted functions in python are stable (and sort is in place). The stability of the sort means the non-zero values remain in the same place.

The time complexity is therefore O(n log n) which is perfectly acceptable. This solution was in fact provided by Stefan Pochmann on Leetcode.

## Using Iteration

Another great approach is to simply iterate through the list, with two pointers, from left to right.

1 def move_zeros_to_end(A):
2   w = 0
3   for r in range(len(A)):
4     if A[w] == 0 and A[r] != 0:
5       A[w], A[r] = A[r], A[w]
6       w += 1
7     elif A[w] != 0:
8       w += 1


If the left pointer's value is zero, and the right pointer's value is non zero, swap them, and increment. Another condition is that if the left pointer is non-zero then it needs to be incremented, since it really needs to be on a zero for a swap to take place.

This solution is in-place, and runs in O(n) so is extremely optimal. However the astute reader will notice that w += 1 takes place whether the left pointer is 0 or not. So what really determines whether we move the left pointer is actually whether the right pointer is non-zero.

1 def move_zeros_to_end(A):
2   w = 0
3   for r in range(len(A)):
4     if A[r] != 0:
5       A[w], A[r] = A[r], A[w]
6       w += 1


This code is now a lot more concise. If you want to start entering code golf territory, then all our assigments can be done on one line:

1 def move_zeros_to_end(A):
2   w = 0
3   for r in range(len(A)):
4     if A[r] != 0:
5       A[w], A[r], w = A[r], A[w], w+1