🎨Now live: Try our Free AI Image Generation Feature

Description
Given an array nums
, write a function that moves all 0
s to the end of it while maintaining the relative order of the non-zero elements. The function should do this in-place without making a copy of the array.
Intuition
The problem can be solved efficiently by using two pointers. The idea is to iterate through the array, and whenever a 0
is found, move it to the end while keeping the relative order of the non-zero elements intact. The key here is to do this in-place without using extra space.
Approach
- Two Pointers Technique: Use two pointers,
l
andr
, wherel
starts at the beginning andr
at the end of the array. - Traverse the array with pointerl
. When a0
is found, shift all elements to the left froml
tor
and place0
at ther
-th position. - Decrement ther
pointer, and updatel
accordingly. - Continue this process untill
surpassesr
. - Optimization: Instead of continuously moving elements, consider maintaining a count of zeros and placing them at the end after traversing the entire array.
Complexity
Time Complexity:
O(n^2)
in the worst case because for every 0
found, the remaining elements are shifted, leading to a quadratic time complexity.
Space Complexity:
O(1)
since the operation is performed in-place without using any extra space.
Code
C++
class Solution {
public:
void moveZeroes(vector& nums) {
int l = 0;
int r = nums.size() - 1;
while (l <= r) {
if (nums[l] == 0) {
int oldVal = l;
while (l < r) {
nums[l] = nums[l + 1];
l++;
}
nums[r] = 0;
r--;
nums[oldVal] == 0 ? l = oldVal : l = oldVal + 1;
} else {
l++;
}
}
}
};
Python
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
l = 0
r = len(nums) - 1
while l <= r:
if nums[l] == 0:
oldVal = l
while l < r:
nums[l] = nums[l + 1]
l += 1
nums[r] = 0
r -= 1
if nums[oldVal] == 0:
l = oldVal
else:
l = oldVal + 1
else:
l += 1
Java
class Solution {
public void moveZeroes(int[] nums) {
int l = 0;
int r = nums.length - 1;
while (l <= r) {
if (nums[l] == 0) {
int oldVal = l;
while (l < r) {
nums[l] = nums[l + 1];
l++;
}
nums[r] = 0;
r--;
if (nums[oldVal] == 0) {
l = oldVal;
} else {
l = oldVal + 1;
}
} else {
l++;
}
}
}
}
JavaScript
var moveZeroes = function (nums) {
let l = 0;
let r = nums.length - 1;
while (l <= r) {
if (nums[l] === 0) {
var oldVal = l;
while (l < r) {
nums[l] = nums[l + 1];
l++;
}
nums[r] = 0;
r--;
nums[oldVal] === 0 ? l = oldVal : l = oldVal + 1;
} else {
l++;
}
}
return nums;
};