Reference: LeetCode
Difficulty: Easy

Problem

Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of 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:

Analysis

Use Extra Space

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

Here is a correct version.

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.

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.
• q could be declared as a local variable inside the while-loop because it always starts by one element after p.

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$.

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$.

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)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.