Problem

Move Zeroes

LeetCode #283Easy

In-place · keep non-zeros in order

Given an integer array, move all zeros to the end in place while keeping the relative order of the non-zero elements.

Asked atMetaAmazonMicrosoft

Brute force · extra array

time O(n)space O(n)

step 1 / 35

Brute force · extra array

Optimized · same-direction two pointers

[0][1][2][3][4]

aux (not yet allocated)

[0][1][2][3][4]

Brute force · extra array


▸
1given arr (n elements)
2aux ← new array of size n filled with 0
3write ← 0
4for i ← 0 to n − 1:
5    if arr[i] ≠ 0:
6        aux[write++] = arr[i]
7copy aux back into arr

state

n5
goal[1, 3, 12, 0, 0]

Move every zero to the end of arr while keeping the relative order of the non-zero elements.

Unrolling loops...

warming up the animation