Approach
This problem is supposed to make use of
two pointers. It may be that I'm still working on my first cup of coffee today but I wanted to try something
different. In my approach I iterate over the vector of nums, moving all the non-zero integers to the beginning. Then
I loop one more time from the last position of a non-zero integer + 1 to the end of nums and place zeroes in
place.
After review, this is not more efficient than the two pointers method. The algorithm still runs on
the order of n for time complexity, but some unecessary iterations happen.
For example, if there is only
one non-zero integer in the nums and it's at the beginning and the nums size is very large i.e. [1, 0, 0, 0,
..., 0], the second loop would run from index 1 - nums.size() placing zeroes where they already exist.
In
hindsight, I should have used left and right pointers and done swaps when non-zero integers were
found.
Complexity
Time Complexity: O(n)
Space Complexity:
O(1)
Code
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int s = nums.size();
int cur = 0;
for(int i = 0; i < s; i++){
if(nums[i] != 0){
nums[cur] = nums[i];
cur++;
}
}
for(int i = cur; i < s; i++){
nums[i] = 0;
}
}
};