Leetcode Problem#283: Move Zeros

Problem
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example:
Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0]

There are many ways to solve this problem. Here I am going to discuss about the optimal solution to tackle the challenge.

Using two pointers approach, we can solve this problem. Pointer One will look for non-zero elements and Pointer Two will swap the elements with Pointer One. We initialize both pointers to 0. Eventually all zero elements will be moved to the end.

Implementation (Java)

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

        int pointer=0;
        int n= nums.length;

        for(int i = 0; i < n; i++){
            if(nums[i]!= 0){
                int temp = nums[i];
                nums[i] = nums[pointer];
                nums[pointer] = temp;
                pointer++;
            }
        }
    }
}

Implementation (PHP)

class Solution {

    /**
     * @param Integer[] $nums
     * @return NULL
     */
    function moveZeroes(&$nums) {
        $pointer = 0;
        $numsLength = count($nums);

        for($i=0; $i<$numsLength; $i++){
            if($nums[$i]!=0){
                $temp = $nums[$i];
                $nums[$i]= $nums[$pointer];
                $nums[$pointer] = $temp;
                $pointer++;
            }
        }
    }
}

Solution Analysis

Time complexity = O(n)
Space complexity = O(1)

Note

Why are we not using Brute Force approach?

Through this approach, we traverse the whole array to find non-zero elements and store them in the starting indexes. And then we fill up the extra spaces with zero. Therefore, we get time complexity in the worst case.

Time Complexity = Time Complexity of filling non-zero elements + Time Complexity of filling zero elements = O(n)+O(n)= O(n)

Space Complexity = O(n) for extra space