Move Zeroes

Given an arraynums, write a function to move all0'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元素时不必要的swap操作，比如

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

第一个循环中，j就会找到第一个非0元素，这里是nums[5] = 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/