Move Zeroes

Intuition

We want to move all zeros to the end of the array while keeping the relative order of non-zero elements.

A naive approach would be to remove zeros and append them at the end, but that may use extra memory or multiple passes. Instead, we can do this in-place by shifting non-zeros forward and filling the rest with zeros.

Approach

Two-Pointer Technique

1. Use a pointer insertPos to track the position where the next non-zero element should be placed.
2. Iterate over the array:

• If nums[i] is non-zero, place it at nums[insertPos] and increment insertPos.

1. After the iteration, fill the rest of the array (insertPos … n-1) with zeros.

Proof of Correctness

• All non-zero elements are copied once to the earliest available position (insertPos), preserving their original relative order.
• The remaining indices after the last non-zero must be zeros (since we overwrite them).
• Thus, the final array has all non-zeros in original order followed by zeros.

Complexity

• Time: O(n) (single pass over the array).
• Space: O(1) (in-place, no extra data structures).

Code

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

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

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

def moveZeroes(self, nums):
        insertPos = 0

        for i in range(len(nums)):
            if nums[i] != 0:
                nums[insertPos] = nums[i]
                insertPos += 1

        while insertPos < len(nums):
            nums[insertPos] = 0
            insertPos += 1