Move Zeroes

• LeetCode: Move Zeroes

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

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [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:

Use two pointers, one is to find the zero and the other is to find non-zero.

• Code - Java:

public class Solution {
    public void moveZeroes(int[] nums) {
        int len = nums.length;
        int left = 0;
        int right = 0;
        while (true) {
            while (left < len  && nums[left] != 0) {
                left++;
            }
            if (left == len) {
                break;
            }
            right = left;
            while (right < len && nums[right] == 0) {
                right++;
            }
            if (right == len) {
                break;
            }
            swap (nums, left, right);
            left++;
        }
    }
    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

• Code - C++:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int size = nums.size();
        int left = 0;
        int right = 0;
        while (true) {
            while (left < size  && nums[left] != 0) {
                left++;
            }
            if (left == size) {
                break;
            }
            right = left;
            while (right < size && nums[right] == 0) {
                right++;
            }
            if (right == size) {
                break;
            }
            swap (nums, left, right);
            left++;
        }
    }
    void swap(vector<int>& nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
};

• Code - Python:

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        left, right, numLen = 0, 0, len(nums)
        while(True):
            while (left < numLen and nums[left] != 0):
                left += 1
            if (left == numLen):
                break
            right = left
            while (right < numLen and nums[right] == 0):
                right += 1
            if (right == numLen):
                break
            self.swap(nums, left, right)
            left += 1

    def swap(self, nums, left, right):
        temp = nums[left]
        nums[left] = nums[right]
        nums[right] = temp

• Code - C:

void moveZeroes(int* nums, int numsSize) {
    int left = 0;
    int right = 0;
    while (true) {
        while (left < numsSize && nums[left] != 0) {
            left++;

        }
        if (left == numsSize) {
            break;
        }
        right = left;
        while (right < numsSize && nums[right] == 0) {
            right++;
        }
        if (right == numsSize) {
            break;
        }
        swap(nums, left, right);
        left++;
    }
}
void swap(int* nums, int left, int right) {
    int temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
}

• Time Complexity: O(N), N is the length of array
• Space Complexity: O(1)