Move Zeroes to the end of the array

Easy

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.

Example:

Input: [0,1,0,3,12]
Output: [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.

The 2 requirements of the question are:

  1. Move all the 0’s to the end of the array.
  2. All the non-zero elements must retain their original order.

It’s good to realize here that both the requirements are mutually exclusive, i.e., you can solve the individual sub-problems and then combine them for the final solution.

This is a 2 pointer approach. The fast pointer which is denoted by variable i does the processing of new elements. If the newly found element is not a 0, we record it just after the last found non-0 element. The position of last found non-0 element is denoted by the slow pointer “lastNonZero” variable.

As we keep finding new non-0 elements, we just overwrite them at the lastNonZero+1'th index. This overwrite will not result in any loss of data because we already processed what was there (if it were non-0,it already is now written at its corresponding index, or if it were 0 it will be handled later in time). 

After the ith index reaches the end of the array, we now know that all the non-0 elements have been moved to the beginning of the array in their original order. Now comes the time to fulfil other requirements, “Move all 0’s to the end”. We now simply need to fill all the indexes after the “lastNonZero” index with 0.

public void moveZeroes(int[] nums) {
    if (nums == null || nums.length == 0) {
        return;
    }
    int lastNonZero = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            nums[lastNonZero] = nums[i];
            lastNonZero++;
        }
    }
    while (lastNonZero < nums.length) {
        nums[lastNonZero++] = 0;
    }
}

Complexity Analysis

Space Complexity: O(1). Only constant space is used.

Time Complexity: O(n). However, the total number of operations is still sub-optimal. The total operations (array writes) that code does is n (Total number of elements).

Categories: Array

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s