Dare2Solve
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.
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.
l
and r
, where l
starts at the beginning and r
at the end of the array.
l
. When a 0
is found, shift all elements to the left from l
to r
and place 0
at the r
-th position.r
pointer, and update l
accordingly.l
surpasses r
.O(n^2)
in the worst case because for every 0
found, the remaining elements are shifted, leading to a quadratic time complexity.
O(1)
since the operation is performed in-place without using any extra space.
class Solution {
public:
void moveZeroes(vector<int>& 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++;
}
}
}
};
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
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++;
}
}
}
}
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;
};