Move Zeroes

Q: 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.

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.

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

The constraint is keeping the other values in their original order, which rules out swapping each 0 with the last element. One index reads every element, a second marks where the next non-zero value belongs, and one pass finishes the job in place.

Copy the non-zero values

Intuition

Copy every non-zero value into a new array in the order you meet it, then add zeros until it is as long as nums. The order is right because you copy values in the order you read them.

Each element is read once and written once: O(n) time, plus O(n) memory for the second array.

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

After every step two facts hold: everything before write is the non-zero values seen so far, in order, and everything from write up to read is 0. A non-zero nums[read] swaps with nums[write], so the value landing at read is a 0, 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, 7 and 2 swap into indexes 0, 1 and 2 in turn, and the zeros end at indexes 3 and 4. 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

Swapping each 0 with the last element. That moves the zeros but scrambles the rest: [0, 4, 7] becomes [7, 4, 0].
Deleting zeros while an index walks over the array. 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²).
Testing x > 0 instead of x != 0. Negative values are not zeros: [-1, 0, -2] must become [-1, -2, 0], but the copy version would return [0, 0, 0].

Frequently asked questions3

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.

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.

def moveZeroes(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

[4, 7, 2, 0, 0]