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]
Constraints:
- 1 <= nums.length <= 104
- -231 <= nums[i] <= 231 - 1
Follow up: Could you minimize the total number of operations done?
Contents
- Solution 1 - Move non-zero elements to the beginning, fill remaining with 0's
In this approach, we will move all non-zero elements to the beginning of the array, then fill remaining with 0's,
say if there are n number of elements in the input array, out of which there are m non-zero elements,
after moving m elements to the beginning, we will be left with m-n spots after that, we will simply fill these with 0's.
For example, consider input array nums = [0,1,0,3,12], we will iterate through the array and move non-zero elements 1, 3, and 12 to left,
so the resultant array looks like
[1,3,12,↑3,12], we have moved 3 non-zero elements 1, 3, 12 to the beginning, array length is 5,
so the remaining elements are 5 -3 =2, we will them with 0's from up arrow, so the final array looks [1,3,12,0,0].
Implementation steps:
-
We will create a variable nonZeroIndex =0, to keep track index where to move non-zero elements.
-
Then, loop through elements of input array nums and if it's a non-zero element update the nums array at index nonZeroIndex,
and increment nonZeroIndex.
-
At the end, nonZeroIndex will be at a position where all non-zero elements are moved to left side of array, now we will fill reamining elements
from nonZeroIndex until end of array with 0's.
import java.util.Arrays;
public class MoveZeroes {
static void moveZeroes(int[] nums) {
int nonZeroIndex = 0;
for(int i=0; i<nums.length; i++) {
if(nums[i] != 0) {
nums[nonZeroIndex] = nums[i];
nonZeroIndex++;
}
}
// fill all remaining elements with 0's from where nonZeroIndex ended till end of array
while(nonZeroIndex<nums.length){
nums[nonZeroIndex] = 0;
nonZeroIndex++;
}
}
public static void main(String[] args) {
int[] nums = {0,1,0,3,12};
moveZeroes(nums);
System.out.println(Arrays.toString(nums));
nums = new int[]{0};
moveZeroes(nums);
System.out.println(Arrays.toString(nums));
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time where n is the length of nums array.
Space complexity: O(1).
Above implementations source code can be found at
GitHub link for Java code