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.

Example1

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

Example2

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

Constraints

  • 1<=nums.length<=104
  • -231<=nums[i]<=231-1

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

SOLVING

We’ll use the Two Pointers method

Steps

  • Rigth and Left Pointer starts at 0
  • Move all around the list by moving the Rigth Pointer
  • If the number is different of zero move the element under Right Pointer to the element under the Left Pointer
 R
 L
 ↓
[0, 1, 0, 3, 12]

 L  R
 ↓  ↓
[0, 1, 0, 3, 12]
Move the 1 at the beginning

    L  R
    ↓  ↓
[1, 1, 0, 3, 12]

    L     R
    ↓     ↓
[1, 1, 0, 3, 12]
Move the 3 at the beginning

       L     R
       ↓     ↓
[1, 3, 0, 3, 12]
Move the 12 at the beginning
  • Now fill the rest of the list by some 0 by moving the Left Pointer to the end
	   L
	   ↓
[1, 3, 12, 3, 12]

	   L
	   ↓
[1, 3, 12, 0, 12]
Replace by a 0

	      L
	      ↓
[1, 3, 12, 0, 0]
Replace by a 0

Code

class Solution {
public:
  void moveZeroes(vector<int> &nums) {
    int size = nums.size() - 1;
    int leftPtr = 0;
    int rightPtr = 0;

    for (; rightPtr <= size; rightPtr++) {
      if (nums[rightPtr] != 0)
	nums[leftPtr++] = nums[rightPtr];
    }

    for (; leftPtr <= size; leftPtr++)
      nums[leftPtr] = 0;
  }
};