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]
By far the simplest solution is to use
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.
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.
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