Reference: LeetCode

Difficulty: Easy

My Post: Java All Solutions with Explanation (Extra Space, Non-Optimal and Optimal Two Pointers)

## Problem

Given an array

`nums`

, write a function to move all`0`

‘s to the end of it while maintaining therelative orderof the non-zero elements.

**Note:**

- You must do this
`in-place`

without making a copy of the array. - Minimize the total number of operations.

**Example:**

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

## Analysis

### Use Extra Space

Here is an incorrect version of this method. Please see the comment.

1 | // extra space (incorrect) |

Here is a correct version.

1 | public void moveZeroes(int[] nums) { |

**Time:** $O(N)$**Space:** $O(N)$

### Two Pointers (Non-Optimal)

Let denote two pointers `p`

and `q`

:

`p`

: Always points to the leftmost zero`q`

: Always points to the first non-zero after`p`

The algorithm is described in the example.

1 | Example: [0, 1, 0, 3, 12] |

**Note:**

- The conditions are
`while (true)`

and`if (q >= n)`

.- We can replace the first one by
`while (p < n)`

, but it is not necessary if we have`if (q >= n)`

inside the loop.`q`

always stays ahead`p`

. By this checking, it also guarantees out-of-bound errors won’t occur in swapping.

- We can replace the first one by
`q`

could be declared as a**local variable**inside the while-loop because it always starts by one element after`p`

.

1 | // two pointers |

**Time:** $O(N^2)$**Space:** $O(1)$

Consider the worst case `[0, 0, 0, 0, 1, 1, 1, 1]`

. The pointer `p`

will go through the first four zeroes (half of all elements), and each time `q`

will go through half of all elements to find the first non-zero element. Therefore, there are approximately $\frac{N}{2} \times \frac{N}{2}$ operations in total. So the runtime is $O(N^2)$.

### Two Pointers (Optimal)

There are two versions. The idea of the first version is simple. Go through `nums`

and put all non-zero elements at the beginning of the array. We use a pointer `lastNonZeroIdx`

to keep track of the subarray we are building. After the first traversal, we set the remaining elements starting from `lastNonZeroIdx`

to $0$.

1 | public void moveZeroes(int[] nums) { |

**Time:** $O(N)$ since the total number of array writes is $N$.**Space:** $O(1)$

The second version is more succinct because we just need to iterate through `nums`

once. Instead of setting the element, we use swapping. To see why it is correct, you can examine two cases:

- Array starts with a zero:
`[0, 1, 0, 3, 12]`

- Array starts with a non-zero:
`[1, 0, 0, 3, 12]`

An intuitive idea is that by swapping we continuously set the elements ahead of `lastNonZeroIdx`

as $0$.

1 | public void moveZeroes(int[] nums) { |

**Time:** $O(N)$ since the number of swapping is determined by the number of non-zero elements. It is especially the case when many elements are zeroes.**Space:** $O(1)$