Move Zeroes

Easy Problem 6 of 151 Java and Python

Practice on LeetCode

Problem

Given an integer array nums, move all 0s to the end while keeping the relative order of the non-zero elements.

Do it in place, without making a copy of the array.

Example 1

Input: nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

Example 2

Input: nums = [0]
Output: [0]

Constraints

1 ≤ nums.length ≤ 10⁴
-2³¹ ≤ nums[i] ≤ 2³¹ – 1

Explanation

Think of the array as two zones: the finished non-zero part at the front, and everything else. A pointer write marks where the next non-zero belongs. Every time the reading pointer finds a non-zero, swap it into write and move write forward.

Approach 1 · Naive

Copy into a temporary array

Time O(n)
Space O(n)

Collect the non-zero values in order, then write them back and fill the rest with zeros. Simple, but it uses extra memory, which the problem asks you to avoid.

Copy every non-zero value into a new list.
Write the list back to the start of nums.
Fill the remaining positions with 0.

Java

class Solution {
    public void moveZeroes(int[] nums) {
        int[] temp = new int[nums.length];
        int k = 0;
        for (int num : nums) {
            if (num != 0) {
                temp[k++] = num;
            }
        }
        // temp is already zero after position k.
        System.arraycopy(temp, 0, nums, 0, nums.length);
    }
}

Python

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        non_zero = [num for num in nums if num != 0]
        zeros = len(nums) - len(non_zero)
        nums[:] = non_zero + [0] * zeros

Approach 2 · Optimal

Two pointers, in place

Time O(n)
Space O(1)

Read every element with one pointer, and swap each non-zero into the position held by a second, slower write pointer.

Set write = 0.
For each index read: if nums[read] != 0, swap nums[read] with nums[write] and increment write.
When the loop ends, all zeros have been pushed behind write.

Java

class Solution {
    public void moveZeroes(int[] nums) {
        int write = 0;
        for (int read = 0; read < nums.length; read++) {
            if (nums[read] != 0) {
                int temp = nums[read];
                nums[read] = nums[write];
                nums[write] = temp;
                write++;
            }
        }
    }
}

Python

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        write = 0
        for read in range(len(nums)):
            if nums[read] != 0:
                nums[read], nums[write] = nums[write], nums[read]
                write += 1

Complexity compared

Approach	Time	Space
Naive Copy into a temporary array	O(n)	O(n)
Optimal Two pointers, in place	O(n)	O(1)

Key takeaways

The read/write pointer pattern also solves Remove Element and Remove Duplicates from Sorted Array.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem