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:
- You must do this in-place without making a copy of the array.
- Minimize the total number of operations.
Solution
One of the solutions is to create new array of the same size as input array. Add the non zero values to the new array. Add zero to the remaining positions at the last. The time complexity is linear, but the space complexity is O(n), n being the size of array.
But we can do this without using that extra array. We keep track of index. And iterate over the array, updating the index position with the current element if current element is not zero. Then looping to make all elements from index to last zero. This will make the space complexity O(1).
/**
* MoveZerosToEnd.java
* Purpose: Move zeros to end.
*
* @author Megha Rastogi
* @version 1.0 07/13/2020
*/
class MoveZerosToEnd {
/**
* Move zeros to end of array
*
* @param Array, nums
*/
public void moveZeroes(int[] nums) {
// track index to keep track of non zero elements
int index = 0;
// Loop through the array and
// if element is not zero make it the
// indexth element
for(int arr_i = 0; arr_i < nums.length; arr_i++) {
if(nums[arr_i] != 0){
nums[index++] = nums[arr_i];
}
}
// Loop from index to end to make the end elements zero
for(int arr_i = index; arr_i < nums.length; arr_i++){
nums[arr_i] = 0;
}
}
}
Source – leetcode
Code – MoveZerosToEnd.java