283. Move Zeroes

Question

LeetCode 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.
Example 1:

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

Example 2:

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?

Solutions

void moveZeros(vector<int> & nums) {
    // two pointer approach:
    // slow pointer points to the position where is to be replaced or not.
    // fast pointer iterates through the array and check if element is not zero. is not zero, then replace it with slow
    // [0, slow) ensures no zero value in this interval.
    // Edge cases:
    // 1. when nums.size is zero: do nothing, return it directly.
    // 2. when nums.size is 1 -> normal processed by the iteration.
    // 3. when all elements are all zero -> fast iterates through all nums and do nothing, and write all zeros again.
    // 4. when no zero -> do N times nums[slow++] = num[fast];
    // Time Complexity: O(N)
    // Space Complexity: O(1)
    int n = static_cast<int>(nums.size());
    int slow = 0;
    if (n == 0) return;
    for (int fast = 0; fast < n; ++fast) {
      if (nums[fast] != 0) {
        nums[slow++] = nums[fast];
      }
    }
    for (int i = slow; i < n; ++i) {
      nums[i] = 0;
    }
}