Move Zeros

Problem Statement

LeetCode-283: 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.

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

Input: nums = [0]
Output: [0]

Input: nums = [5]
Output: [5]

Approach

There are multiple ways to solve this problem.

1. The most intuitive way is to iterate over the array and keep track of the number of zeros encountered.
2. Once we have the count of zeros, we can iterate over the array again and move all the non-zero elements to the front of the array.
3. Finally, we can fill the remaining elements with zeros.

This approach requires two passes over the array and is not optimal.

Another approach is to use two pointers.

1. We can iterate over the array with the first pointer and keep track of the position where the next non-zero element should be placed.
2. We can use the second pointer to iterate over the array and swap the elements at the first and second pointers if the element at the second pointer is non-zero.
3. This way, we can move all the non-zero elements to the front of the array.

Implementation

Let’s implement the two-pointer approach to solve this problem.

public void moveZeroes(int[] nums) {
    int index = 0;
    for(int i=0; i < nums.length; i++){
        if(nums[i] != 0){
            nums[index] = nums[i];
            if(i != index){
                nums[i] = 0;
            }   
            index++;             
        }
    }
}

Note that we only increment the index when we encounter a non-zero element. This way, we can maintain the relative order of the non-zero elements.

Also, we set the element at current index i to 0 only if it is not equal to index as otherwise it will override the just set value. Consider a single element array for this case: [5]

Complexity Analysis

The time complexity for this approach is $O(n)$, where $n$ is the number of elements in the array. We iterate over the array only once.