AlgoViz
HomeArrays & Hashing

Move Zeros to End

Easy

Write the non-zeros forward, then pad

Problem

Given an integer array nums, move all the 0's to the end of the array. The relative order of the other elements must remain the same. This must be done in place, without making a copy of the array.

In simple words

Slide every non-zero forward with a writer pointer, then fill the rest with zeros.

The idea

Sweep once copying every non-zero element to a write pointer, then fill the rest of the array with zeros. Because non-zeros are copied in the order they are met, their relative order is preserved for free.

The trick

  • The write pointer counts the non-zeros as it goes.
  • Swapping instead of copying does it in a single pass with no fill step.
  • O(n) time, O(1) space.
i
j
0
1
0
3
12
0
1
2
3
4

Step 1 of 6. Zero at 0 → skip, wait for a non-zero. Values: 0, 1, 0, 3, 12. Pointers: i at index 0, j at index 0.

1/6
Optimal
timeO(n)spaceO(1)
1j = 0                       // next slot for a non-zero2for i in 0..n-1:3  if nums[i] != 0:4    swap(nums[i], nums[j]); j++

Input

array
[0, 1, 0, 3, 12]

Memory

i
= 0 [0]
j
= 0 [0]

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [0, 1, 0, 3, 12]
Output:
[1, 3, 12, 0, 0]
Explanation:
Non-zeros keep order, zeros slide to the back.

Example 2

Input:
nums = [0, 0, 1]
Output:
[1, 0, 0]
Explanation:
The single 1 moves to the front.

Example 3

Input:
nums = [1, 2, 3]
Output:
[1, 2, 3]
Explanation:
No zeros, so nothing moves.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <=nums[i] <= 10^4

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.