Move All Zeros to End

Difficulty: Easy

Problem

You are given an integer array. Shift every 0 to the back while the non-zero values keep the same relative order. Do it in-place, without building a second array.

Example

Input: nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]
Explanation: The non-zero values 1, 3, 12 stay in their original order at the front, and both zeros are pushed to the back.

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)

Pseudocode

function moveZeroes(nums):
    insertPos = 0
    
    for each num in nums:
        if num != 0:
            nums[insertPos] = num
            insertPos++
    
    while insertPos < length:
        nums[insertPos] = 0
        insertPos++

Hints

  • Track where the next non-zero should be placed
  • All non-zeros shift left, zeros naturally fill remaining spots
  • Single pass through the array is sufficient

Complexity questions

What is the time complexity of the brute force approach?

O(n). We traverse the array once to collect non-zeros O(n), and once to rebuild O(n). Total: O(n).

What is the space complexity of the brute force approach?

O(n). The temporary array can hold up to n elements (if no zeros), so space is O(n).

What is the time complexity of the optimal approach?

O(n). Single pass to move non-zeros, then fill zeros. O(n) total.

What is the space complexity of the optimal approach?

O(1). Only uses a single pointer variable (insertPos). True in-place solution with O(1) space!

Check your understanding of Move All Zeros to End

Should the relative order of non-zero elements be preserved?

Yes. The problem explicitly requires maintaining the relative order of non-zero elements. [0,1,0,3,12] becomes [1,3,12,0,0], not [12,3,1,0,0].

Is creating a new array allowed for the optimal solution?

No, it must be in-place. The problem requires an in-place solution, modifying the original array without using extra space proportional to input size.

What should happen to zero elements?

Moved to the end. All zeros are moved to the end while non-zeros keep their relative order.

Related problems

Keep practising