Problem
Given an integer array nums, move all0s to the end of the array while maintaining the relative order of the non-zero elements. The operation must be performed in-place without making a copy of the array.
Example(s)
Consider the following example(s) to understand the expected input and output.Example 1
Input
nums = [0,1,0,3,12]Output
[1,3,12,0,0]Example 2
Input
nums = [0,0,1]Output
[1,0,0]Solution
This solution uses a Two Pointer approach. Thei pointer scans the entire array, while the write pointer keeps track of the next position where a non-zero element should be placed.
Whenever
nums[i] is non-zero, we copy it to nums[write] and increment write. This moves all non-zero elements to the beginning of the array while preserving their relative order.
After all non-zero elements have been processed,
write points to the first position that should contain a zero. We then fill all remaining positions with 0.
This approach modifies the array in-place without requiring an additional array.
class Solution {
public void moveZeroes(int[] nums) {
int write = 0;
int i = 0;
int n = nums.length;
while (i < n) {
if (nums[i] != 0) {
nums[write++] = nums[i];
}
i++;
}
for (i = write; i < n; i++) {
nums[i] = 0;
}
}
}Complexity
The array is traversed once to move the non-zero elements and once to fill the remaining positions with zeroes. Therefore, the time complexity isO(n).
The solution modifies the input array directly and uses only a few variables, so the extra space complexity is
O(1).