Move Zeroes

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.

Example:

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

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

Analysis

Two Pointers两个指针

i - slow pointer, 需要被替换写入的index，当前元素为0，可以看成insert position

j - fast pointer, 下一个非0元素，将被换到i的位置

``````[0, 0, 0, 0, 0, 1]
``````

i会找到第一个需要被替换的0元素位置，这里是nums[0] = 0;

Solution

Two Pointers - Fast & Slow

``````class Solution {
public void moveZeroes(int[] nums) {
int n = nums.length;
int i = 0, j = 0;
while (i < n && j < n) {
// j is the index of next non-zero element
while (j < n && nums[j] == 0) {
j++;
}
// i is the insert position
while (i < j && nums[i] != 0) {
i++;
}
if (i < n && j < n) {
swap(nums, i, j);
j++;
i++;
}
}
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
``````

Insert Index - Swap (LeetCode Official Solution)

the code will maintain the following invariant:

1. All elements before the slow pointer (lastNonZeroFoundAt) are non-zeroes.

2. All elements between the current and slow pointer are zeroes.

Therefore, when we encounter a non-zero element, we need to swap elements pointed by current and slow pointer, then advance both pointers. If it's zero element, we just advance current pointer.

Complexity:

O(n) time

O(1) space

``````class Solution {
public void moveZeroes(int[] nums) {

int j = 0;
for(int i = 0; i < nums.length; i++) {
if(nums[i] != 0) {
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
j++;
}
}
}
}
``````

Ref

https://leetcode.com/problems/move-zeroes/discuss/72000/1ms-Java-solution/74551

``````public void moveZeroes(int[] nums) {
int leftMostZeroIndex = 0; // The index of the leftmost zero
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
if (i > leftMostZeroIndex) { // There are zero(s) on the left side of the current non-zero number, swap!
nums[leftMostZeroIndex] = nums[i];
nums[i] = 0;
}

leftMostZeroIndex++;
}
}
}
``````

Reference

https://leetcode.com/problems/move-zeroes/solution/