Move Zeroes

(#283), Easy

Category: Array, Two Pointer

Problem Statement

Given an integer array `nums`, move all 0's to the end of it while maintaining the relative order of the non-zero elements. You must do this in-place without making a copy of the array.

Examples

Input: [0,1,0,3,12]

Output: [1,3,12,0,0]

Input: [0]

Output: [0]

Approach

Approach 1: Using Extra Space

  • Iterate through the array and collect all non-zero elements in a new array.
  • Overwrite the original array with these non-zero elements.
  • Fill the remaining positions in the array with zeroes.
// Approach 1: Using extra space
var moveZeroes = function (nums) {
  let nonZeroes = [];

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      nonZeroes.push(nums[i]);
    }
  }

  let i = 0;
  while (i < nonZeroes.length) {
    nums[i] = nonZeroes[i];
    i++;
  }

  while (i < nums.length) {
    nums[i] = 0;
    i++;
  }

  return nums;
};

Approach 2: In-place Using Two Pointers

  • Initialize two pointers `first = 0` and `sec = 1`.
  • If `nums[first]` is 0 and `nums[sec]` is not, swap them.
  • If both are 0, move `sec` only.
  • Otherwise, move both pointers forward.
  • Repeat until the array is rearranged with all zeroes at the end.
// Approach 2: In-place using Two Pointers
var moveZeroes = function (nums) {
  let first = 0;
  let sec = 1;

  while (first < sec && sec < nums.length) {
    if (nums[first] === 0 && nums[sec] !== 0) {
      [nums[first], nums[sec]] = [nums[sec], nums[first]];
      first++;
      sec++;
    } else if (nums[first] === 0 && nums[sec] === 0) {
      sec++;
    } else {
      first++;
      sec++;
    }
  }
};

Complexity

Time: O(n)

Space: O(1) for in-place solution, O(n) for brute force

Watch Explanation

📊 Presentation (PPT)

📥 Download PPT

📎 Resources