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

1
2
Input:  [0,1,0,3,12]
Output: [1,3,12,0,0]

Analysis

Use Extra Space

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

1
2
3
4
5
6
7
8
9
10
11
12
// extra space (incorrect)
public void moveZeroes(int[] nums) {
  int n = nums.length;
  int[] result = new int[n];
  int count = 0;
  for (int i = 0; i < n; ++i) {
    if (nums[i] != 0) {
      result[count++] = nums[i];
    }
  }
  nums = result; // not okay (the reference outside of this function is not changed)
}

Here is a correct version.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void moveZeroes(int[] nums) {
  int n = nums.length;
  List<Integer> extra = new ArrayList<>();
  for (int i = 0; i < n; ++i) {
    if (nums[i] != 0) {
      extra.add(nums[i]);
    }
  }
  // put that numbers to nums
  int i = 0;
  for (i = 0; i < extra.size(); ++i) {
    nums[i] = extra.get(i);
  }
  // put zeroes
  while (i < n) {
    nums[i] = 0;
    ++i;
  }
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Example: [0, 1, 0, 3, 12]

0, 1, 0, 3, 12
p->p
   q
1, 0, 0, 3, 12
after swapping, p moves on by one step and goes to the next round 

1, 0, 0, 3, 12 (p hits 0 immediately)
   p->p
      q->q
1, 3, 0, 0, 12
after swapping, p moves on by one step and goes to the next round

1, 3, 0, 0, 12
      p->p
         q->q
1, 3, 12,0, 0
after swapping, p moves on by one step and goes to the next round

Now p hits 0 again, but we cannot stop. We stop when q hits the end of the array, which means after p we cannot find an non-zero element. In other words, all elements after p are zeroes. So we stop.

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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// two pointers
// 0  1  0  3  12
public void moveZeroes(int[] nums) {
  int n = nums.length;
  int p = 0; // p --> current 0
  // condition ends at when q >= n
  while (true) {
    while (p < n && nums[p] != 0) p += 1; // update p
    int q = p + 1;
    while (q < n && nums[q] == 0) q += 1; // update q
    // check ending
    if (q >= n) break; // ends (Invariant:if p >= n, q must also satisfy q >= n)
    // swap
    swap(nums, p, q);
    p += 1; // do not update q
  }
}

private void swap(int[] nums, int i, int j) {
  int temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

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
2
3
4
5
6
7
8
9
10
11
12
13
public void moveZeroes(int[] nums) {
  int n = nums.length;
  int lastNonZeroIdx = 0;
  for (int i = 0; i < n; ++i) {
    if (nums[i] != 0) {
      nums[lastNonZeroIdx++] = nums[i];
    }
  }
  // set the rest elements as Zero
  for (int i = lastNonZeroIdx; i < n; ++i) {
    nums[i] = 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$.

1
2
3
4
5
6
7
8
9
public void moveZeroes(int[] nums) {
  int n = nums.length;
  int lastNonZeroIdx = 0;
  for (int i = 0; i < n; ++i) {
    if (nums[i] != 0) {
      swap(nums, lastNonZeroIdx++, i);
    }
  }
}

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