Move All Zeros to End

Difficulty: Easy

Problem

Given an array of integers, move all 0s to the end of the array without changing the order of non-zero elements. You must do this in-place.

Example

Input: nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]
Explanation: All non-zero elements maintain their relative order, and all zeros are moved to the end.

Brute-force approach

Create a temporary list for non-zeros, count zeros, then rebuild the array.

Steps

  1. Create an empty list for non-zero elements
  2. Traverse array and collect all non-zeros
  3. Calculate zero count = original length - non-zero count
  4. Copy non-zeros back to original array
  5. Fill remaining positions with zeros

Time complexity: O(n) · Space complexity: O(n)

Trade-offs

  • Uses O(n) extra space for temporary array
  • Not truly in-place as required by the problem
  • Two passes: one to collect, one to rebuild

Optimal approach

Key insight: By maintaining an insertPos pointer, we can overwrite the array in-place. Each non-zero moves to insertPos, then we fill the rest with zeros. This achieves O(1) space.

Use a single pointer (insertPos) to track where the next non-zero should go.

Steps

  1. Initialize insertPos = 0
  2. Traverse array with index i
  3. If nums[i] is non-zero, place it at nums[insertPos] and increment insertPos
  4. After traversal, fill positions from insertPos to end with zeros

Time complexity: O(n) · Space complexity: O(1)