In-place Algorithm to Move Zeros to End of List

Given a list of integers nums, put all the zeros to the back of the list by modifying the list in-place. The relative ordering of other elements should stay the same. Can you do it in O(1) additional space?

Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [0, 1, 0, 2, 3]
Output
[1, 2, 3, 0, 0]
Explanation
Note that [1, 2, 3] appear in the same order as in the input.

Two Pointer to Move Zeros to End in Place

The key to solve this problem in-place using O(1) constant space is to use two pointers. One goes through each element one by one and another marks the next place to write if non-zero.

1
2
3
4
5
6
7
8
9
10
11
12

vector<int> solve(vector<int>& nums) {
    int j = 0;
    for (int i = 0; i < nums.size(); ++ i) {
        if (nums[i] != 0) {
            swap(nums[i], nums[j ++]);
        }
    }
    while (j < nums.size()) {
        nums[j ++] = 0;
    }
    return nums;
}

vector<int> solve(vector<int>& nums) {
    int j = 0;
    for (int i = 0; i < nums.size(); ++ i) {
        if (nums[i] != 0) {
            swap(nums[i], nums[j ++]);
        }
    }
    while (j < nums.size()) {
        nums[j ++] = 0;
    }
    return nums;
}

And don’t forget to clear the rest of the array zeros once we have move forward all non-zero elements. This algorithm takes O(N) time and O(1) space.

–EOF (The Ultimate Computing & Technology Blog) —