# 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 `sorted`

makes 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
```