283 - Move Zeroes

Problem

Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Input: nums = [0]
Output: [0]

Constraints:

• 1 <= nums.length <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

Follow-up: could you minimize the total number of operations done?

Approach

Two Pointers with a Swap

Send the non-zero forward and let the same operation carry whatever was sitting there back to j. The thing at nums[i] is always either a zero or nums[j] itself, so the swap can never lose a value or disturb the order of the non-zeros.

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        const int n = nums.size();
        int i = 0;
        for (int j = 0; j < n; j++)
            if (nums[j] != 0) {
                if (i != j) swap(nums[i], nums[j]);
                i++;
            }
    }
};

nums = [0, 1, 0, 3, 12]
j=0  0            skip
j=1  1   swap(0,1) -> [1, 0, 0, 3, 12]   i=1
j=2  0            skip
j=3  3   swap(1,3) -> [1, 3, 0, 0, 12]   i=2
j=4  12  swap(2,4) -> [1, 3, 12, 0, 0]   i=3

• time: O(n) — one pass, j never goes back
• space: O(1) — in place, two indices

On minimizing operations

The copy-and-fill version is the other natural answer:

int i = 0;
for (int j = 0; j < n; j++)
    if (nums[j] != 0) nums[i++] = nums[j];
while (i < n) nums[i++] = 0;