move zeroes to end

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

If a list, e.g

1A = [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?

1A = [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.

1def 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.

1def 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.

1def 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:

1def 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