Move Zeroes

Q: How do you move zeros to the end without changing the order of the other elements?

Keep a write index for the next free spot at the front and scan with a second index. Each non-zero value you find is swapped into the write spot, and write moves one step right. Values are placed in the order you find them, so their relative order never changes.

Q: Can Move Zeroes be done with fewer writes?

Yes. Instead of swapping, copy each non-zero value to nums[write] , and after the scan fill every spot from write to the end with 0. That writes each position at most once. You can also skip a swap when read equals write , since it would put a value back where it already is.

EasyTwo pointers

+10

You get an array of integers nums. Move every 0 to the end of the array and keep the other values in the order they had. Return the rearranged array, which has the same length as nums.

Function

moveZeroes(nums: integer-array) → integer-array

numsinteger-array: the array of integers to rearrange
Returnsinteger-array: nums with the non-zero values first, in their original order, and every 0 at the end

Constraints

1 ≤ nums.length ≤ 5000
-10⁵ ≤ nums[i] ≤ 10⁵

Examples

Input: nums = [0, 4, 0, 7, 2]
Output: [4, 7, 2, 0, 0]
Explanation: The values that are not 0 are 4, 7 and 2, and they keep that order at the front. The two 0s fill the last two places.

+14 hidden tests on Submit

Follow-up

Can you move every 0 to the front instead, keeping the other values in their order, in one pass with O(1) extra memory?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Getting the zeros to the end is not the hard part. Keeping the other values in their original order is, and it rules out swapping each 0 with the last element. Split the array into a front zone that holds the non-zero values found so far and the rest. One index reads every element, a second marks where the next non-zero value belongs, and a single pass finishes the job in place.

Copy the non-zero values

Intuition

Build a new array. Walk through nums and copy every value that is not 0, in the order you meet it. Then add zeros until the new array is as long as nums. The number of zeros you add is the number you skipped.

For [0, 4, 0, 7, 2] the copy step gives [4, 7, 2], and two zeros make it [4, 7, 2, 0, 0]. The order is right because you copy values in the order you read them.

Each element is read once and written once, so the time is O(n). The second array costs O(n) memory, which the next approach avoids.

Algorithm

Create an empty result array.
For each value in nums, append it to the result if it is not 0.
Append zeros until the result has as many entries as nums.
Return the result.

def moveZeroes(nums):
    result = [x for x in nums if x != 0]
    result += [0] * (len(nums) - len(result))
    return result

Two pointers, swapping in place

Intuition

Use two indices. read visits every element from left to right. write marks where the next non-zero value belongs. After every step, two facts hold: everything before write is the non-zero values seen so far, in their original order, and everything from write up to read is 0.

When nums[read] is not 0, swap it with nums[write] and move write one step right. The value that lands at read is a 0 from the zero zone, or the same value when the two indices are equal. Non-zero values only jump over zeros, never over each other, so their order is kept.

On [0, 4, 0, 7, 2]: the 4 at index 1 swaps with index 0, giving [4, 0, 0, 7, 2]. The 7 at index 3 swaps with index 1, giving [4, 7, 0, 0, 2]. The 2 at index 4 swaps with index 2, giving [4, 7, 2, 0, 0]. One pass and no second array: O(n) time and O(1) memory.

Algorithm

Set write to 0.
Move read from the first index to the last.
If nums[read] is not 0, swap nums[read] with nums[write], then add 1 to write.
Return nums.

def moveZeroes(nums):
    write = 0  # nums[:write] holds the non-zero values found so far, in order
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

Pitfalls and edge cases

The usual bugs either break the order of the other values or skip elements.

Swapping each 0 with the last element moves the zeros but scrambles the rest: [0, 4, 7] becomes [7, 4, 0].
Deleting zeros from the array while an index walks over it skips elements. In [0, 0, 5], deleting index 0 slides the second 0 into index 0 while the loop moves on to index 1. Each deletion also shifts the rest of the array, which makes the loop O(n²).
Test x != 0, not x > 0. Negative values are not zeros: [-1, 0, -2] must become [-1, -2, 0], but with x > 0 the copy version returns [0, 0, 0].
An array with no zeros, or with only zeros, must come back unchanged. In the swap version read and write stay equal until the first 0, so those swaps change nothing.
In Lua and R, arrays start at 1, so write starts at 1 too.

Frequently asked questions4

What is the time complexity of Move Zeroes?

O(n). Both approaches read each element once. Copying the non-zero values into a new array needs O(n) extra memory, while the two pointer swap works inside the array with O(1) extra memory.

How do you move zeros to the end without changing the order of the other elements?

Keep a write index for the next free spot at the front and scan with a second index. Each non-zero value you find is swapped into the write spot, and write moves one step right. Values are placed in the order you find them, so their relative order never changes.

Can Move Zeroes be done with fewer writes?

Yes. Instead of swapping, copy each non-zero value to nums[write], and after the scan fill every spot from write to the end with 0. That writes each position at most once. You can also skip a swap when read equals write, since it would put a value back where it already is.

Why is Move Zeroes a two pointer problem?

One pointer reads every element and the other marks the end of the finished front part. Both only move forward, so together they make a single pass. The same read and write pattern removes duplicates from a sorted array or filters any value out of an array in place.

Python

def moveZeroes(nums):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

nums = [0, 4, 0, 7, 2]

Expected

[4, 7, 2, 0, 0]