Leetcode - Move Zeroes

February 7th, 2024
Description

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
Solution

My first thought when coming up with the solution for this problem was that I didn't actually need to move the zeroes. We can simply fill in the beginning of the array with the non-zero numbers, then fill in the remainder with 0s. I can elaborate on this.

We can iterate through the entirety of array nums. We'll keep track of a position pos for the location the next non-zero number would go. Every time we encounter a non-zero number, we'll write the number to nums at pos. We'll then iterate pos by one to indicate the next postion we want to write to in nums. This way, we'll ensure that all of the non-zero numbers are in beginning.

Now, what about the zeros? We still have pos to track where our next number goes. We've already established where the non-zero numbers go. We can simply just fill in the rest of the array with zeros and call it a day!

function moveZeroes(nums: number[]): void {
    let pos = 0;

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

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

This code has a runtime of 75 ms and a memory usage of 55.5 MB.