Leetcode 283: Move Zeroes

This content originally appeared on DEV Community and was authored by Tochi

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.

Explanation

An in-place algorithm modifies the original array directly instead of creating a separate one. You only use a few extra variables (constant space). This is important in Data Structures and Algorithms (DSA) because it saves memory.

What this challenge means is, send all the zeros to the right and all the non-zero items in the array without changing the order of the non-zero items. So, if you have [5,0,1,9,0,6] the output will be [5,1,9,6,0,0].

The Approach

Initially, I solved this using a nested for loop. I compared each item in the array with the next one, and whenever I found a 0, I swapped it forward until it reached the end of the array. While this worked, it was inefficient because the nested loop made the solution run in O(n²) time. For larger arrays, this approach quickly becomes slow.

After tons of research, I was able to optimize my solution using the two pointer method. To do that:

1. Pointer 1 (pointer1) → keeps track of the position where the next non-zero element should go.

2. Pointer 2 (i) → scans through every element of the array.

When we see a non-zero element, we swap it with the element at pointer1. After swapping, we move pointer1 forward by one. If the element is 0, we simply skip it. By the end of the loop, all non-zero numbers are shifted to the left in their original order, and all zeroes are pushed to the right.

The Solution

Solution 1

const moveZeroes = (nums) => {
 if(nums.length === 1){
    return nums;
  }

  for (let j = 0; j < nums.length; j++) {
    for (let i = 0; i < nums.length - 1; i++) {
      if (nums[i] === 0) {
        [nums[i], nums[i + 1]] = [nums[i + 1], nums[i]];
      }
    }
  }

  return nums;
};

console.log(moveZeroes([4, 1, 0, 3, 12])); => [4,1,3,12,0]

The solution above uses nested loop.

Solution 2

const moveZeroes = (nums) => {
  let pointer1= 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      [nums[pointer1], nums[i]] = [nums[i], nums[pointer1]];
      pointer1++;
    }
  }
  return nums;
};
console.log(moveZeroes([4, 1, 0, 3, 12]));=>[4,1,3,12,0]

Solution 2 Explanation

First remember that pointer1 = 0, is where the next non-zero should go.

1. Look at first number(4).
   • Not zero → put it at index 0.
   • Swap index 0 with index 0 → no change.
   • Array: [4, 1, 0, 3, 12]
   • pointer1 = 1
2. Look at second number(1)
   • Not zero → put it at index 1.
   • Swap index 1 with index 1 → no change.
   • Array: [4, 1, 0, 3, 12]
   • pointer1 = 2
3. Look at third number(0)
   • It’s zero → do nothing.
   • Array stays: [4, 1, 0, 3, 12]
   • pointer1 = 2 (stays 2 because the if block did not run).
4. Look at fourth number(3)
   • Not zero → put it at index 2.
   • Swap index 2 with index 3 → [4, 1, 3, 0, 12]
   • pointer1 = 3
5. Look at fifth number(12)
   • Not zero → put it at index 3.
   • Swap index 3 with index 4 → [4, 1, 3, 12, 0]
   • pointer1 = 4

The final result: [4, 1, 3, 12, 0]

The Conclusion

The time complexity for the initial solution (using the nested loops) is O(n²) because for every element in the array, we scan through the entire array again. The optimized solution runs in O(n) time since we only pass through the array once.

Both solutions are in-place and use O(1) extra space, but the optimized version is much faster and more practical for larger arrays.

This content originally appeared on DEV Community and was authored by Tochi