[Leetcode] – Move zeroes Solution

1.3K

In the given problem statement, we have an integer array that may or may not have some zeroes. You need to move all the zeroes to the right of the array without disturbing the original order of all the remaining elements. We desire a space complexity of O(1).

Let us understand the problem easily by a test case.

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

Brute Force Solution:

A pretty straight forward way to solve this problem could be to create 2 different arrays:

• store all the non-zero elements in one array
• the other array holds all the zeroes

Once, we have these 2 arrays, iterate from the first element in the array. If we get a non-zero element, move it to the first array, and if the element is a 0 move it to the second array.

As the loop ends, the relative order of original elements is maintained in the first array. All the zeroes move to the second array. As a last step, merge both the arrays to get the correct answer.

This approach works in a O(n) time, and takes O(n) space as well to store the elements. Surely we can improve on that.

Space Efficient Solution:

Thinking about the problem a little more, we do not have to do anything with the zeroes as long as we maintain the relative order of the other elements. This signals firstly that we do not need any extra space to store the zeroes.

A very simple approach will be:

• Start from the first element in the array, and keep a marker.
• For an element that is non-zero, move the marker ahead as we want to keep the number.
• If the element is zero, just move ahead in the array and leave the marker in the original place.

• Iterate through each element and apply the same logic at every element
• If the array had only 3 non-zero elements, the marker will be at the third position in the array.
• All the rest elements can be substituted with a 0

Theoretically, we did move all zeroes to the end of the array. This method works in-place without taking any extra space.

Code:

  public void moveZeroes(int[] nums) {

    // Start with the first position
    int insertPosition = 0;

    for (int i = 0; i < nums.length; i++) {
      // Fill all non-zero numbers
      if (nums[i] != 0) {
        nums[insertPosition] = nums[i];
        insertPosition++;
      }
    }

    while (insertPosition < nums.length) {
      nums[insertPosition++] = 0;
    }
  }
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(1)

Video Explanation: