Approach 1: Swapping
Pretty straightforward approach where we use two pointers. First pointer, i, iterates through the array normally and the other pointer is used like an “anchor” which points to zero to be swapped (b/w index 0..i).
Long code for better understanding:
void moveZeroes(vector<int>& nums) {
int anchor = 0, i = 0, size = nums.size();
while (i<size) {
// swap 0 with element at index i
if (nums[anchor] == 0 && nums[i] != 0) {
nums[anchor] = nums[i];
nums[i] = 0;
}
// if anchor not pointing to 0, move anchor
if (nums[anchor] != 0)
anchor++;
i++;
}
}
Example:
Input = [0,1,0,3,12]
i=0, anchor=0: no if statement satisfied, i++
i=1, anchor=0: first if statement satisfied, swap. Then second if statement satisfied, do anchor++.
input=[1,0,0,3,12], i=2, anchor=1: no if statement satisfied, i++
input=[1,0,0,3,12], i=3, anchor=1: first if statement satisfied, swap. Then second if statement satisfied, do anchor++.
input=[1,3,0,0,12], i=4, anchor=2: first if statement satisfied, swap. Then second if statement satisfied, do anchor++.
input = [1,3,12,0,0]
Short code:
void moveZeroes(vector<int>& nums) {
for (int i=0, j=0; i<nums.size(); i++) {
if (nums[i] != 0)
swap(nums[i], nums[j++]);
}
}
Time complexity: O(n) Space complexity: O(1)
Approach 2: Overwriting elements
Similar to the above approach, start from the first index keeping two points p1 and p2. p2 traverses the list normally. If p2 is pointing to a non-zero element, overwrite p1 with value at p2 and increment p1. After traversing the whole list, replace elements from p1..p2-1 with 0.
Example:
Input = [0,1,0,3,12]
p1=0, p2=0: do nothing
p1=0, p2=1: replace input[0] with input[1] and do p1++. input = [1,1,0,3,12]
p1=1, p2=2: do nothing
p1=1, p2=3: replace input[1] with input[3] and do p1++. input = [1,3,0,3,12]
p1=2, p2=4: replace input[2] with input[4] and do p1++. input = [1,3,12,3,12]
Now, replace elements from p1..p2-1, i.e., index 2 to 3 with 0. So input becomes [1,3,12,0,0]
Time complexity: O(n) Space complexity: O(1)