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.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

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

public class Solution {
    public void moveZeroes(int[] nums) {
        /** Define two pointers, left point to the last non-zero number on the left part.
          * right points to the first non-zero number on the right part.
          * If right pointer finds non-zero one, swap with i+1, if finds a 0, move right until non-zero one;
          * If left pointer finds 0, move right until
          */
        if (nums == null || nums.length == 0) {
            return;
        }
        int right = 0;
        int left = 0;

        while (right < nums.length) {
            if (nums[right] != 0) {
                while (nums[left] != 0 && left < right) { // Must guarante left is less than right
                    left++;
                }
                // swap(int left, int right) will not work, because it cannot swap values in nums[]
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
            }
            right++;
        }
    }
}
Advertisements