Move Zeroes

Easy#283same direction

You get an array of numbers. Move every zero to the end and keep the other numbers in the order they were in. Do it inside the same array, without a second one. Our example: [0, 4, 0, 0, 7, 2] → [4, 7, 2, 0, 0, 0].

283 Move ZeroesWalkthrough · 1×

Example: [0, 4, 0, 0, 7, 2]. Both pointers walk right: read looks at every number, write marks where the next non-zero one goes.

001420304752write
non-zero, in placebeing readjust swappedzeroesnot read yet

write = 0: the next non-zero number goes to index 0

01/21
restart · back · play · step
Speed
1function moveZeroes(nums):
2 write = 0
3 for read from 0 to len(nums) - 1:
4 if nums[read] != 0:
5 swap nums[write] and nums[read]
6 write = write + 1
7 return nums
state
write
0
read
–
nums
[0, 4, 0, 0, 7, 2]
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Left of write lie only the non-zero numbers met so far, in the order read met them. Each new one is put right after them, so the order cannot change.
  2. Between write and read lie only zeroes. So the swap always trades a zero for the number at read, and no non-zero number is lost or jumps over another.
  3. When read reaches the end, every non-zero number is left of write, and every cell from write onwards holds a zero.

Complexity

Time O(n): read passes the array once, and each step does at most one swap. Memory O(1): the numbers move inside the same array.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.