Move Zeroes

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

You may view the full question here.

Approach 1: Let’s start with the obvious approach — swap your way through the list!

//Approach 1:
//Runtime: 13ms
//Memory usage: 38.4MB
class Solution {
    public void moveZeroes(int[] nums) {
        for(int i = nums.length-2; i >= 0; i--){
            if(nums[i]==0){
                move(nums, i);
            }
        }
    }
    
    private void move(int[] nums, int i){
        while((i+1)<nums.length){
            if(nums[i+1]==0){
                break;
            }
            int temp = nums[i+1];
            nums[i+1] = nums[i];
            nums[i] = temp;
            i++;
        }
    }
}

Clearly, not the fastest approach.

Approach 2: The problem with the previous approach was that we were trying to be pedantic. Instead, a small little tweak is just moving all the non-zero values to one side and resetting all the other values on the other side to zero does the exact job, just 10 times faster! Thanks to this brilliant post here.

//Approach 2:
//Runtime: 0ms
//Memory usage: 36.5MB
class Solution {
    public void moveZeroes(int[] nums) {
        int resIndex = 0;
        for(int i = 0; i<nums.length; i++){
            if(nums[i]!=0){
                nums[resIndex] = nums[i];
                resIndex++;
            }
        }
        for(int i = resIndex; i<nums.length; i++){
            nums[i] = 0;
        }
    }
}

Find more posts here.

Cheers & Chao!