Move Zeroes

Difficulty: Easy | Acceptance: 63.80% | Paid: No Topics: Array, Two Pointers

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

Note that you must do this in-place without making a copy of the array.

• Examples
• Constraints
• Approach 1: Extra Space
• Approach 2: Snowball / Overwrite
• Approach 3: Two Pointers (Optimal)

Examples

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^4
- -2^31 <= nums[i] <= 2^31 - 1

Approach 1: Extra Space

Intuition Create a new list containing all non-zero elements in order, append the required number of zeros to the end, and then copy this new list back into the original array.

Steps

• Iterate through the input array and collect all non-zero elements into a temporary list.
• Calculate the number of zeros needed (length of original array minus length of temporary list).
• Append that many zeros to the temporary list.
• Copy elements from the temporary list back into the original array.

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

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Uses extra memory proportional to the input size, which violates the strict “in-place” constraint if interpreted strictly, though it modifies the original array at the end.

Approach 2: Snowball / Overwrite

Intuition Use a pointer to track the position where the next non-zero element should be placed. Iterate through the array, moving non-zero elements to the front, then fill the remaining positions with zeros.

Steps

• Initialize a pointer insertPos to 0.
• Loop through the array. If the current element is not 0, assign it to nums[insertPos] and increment insertPos.
• After the loop, fill the rest of the array from insertPos to the end with 0s.

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

Complexity

• Time: O(n)
• Space: O(1)
• Notes: True in-place operation. It requires two passes (one to move non-zeros, one to fill zeros).

Approach 3: Two Pointers (Optimal)

Intuition Optimize the previous approach by swapping elements. Instead of a second loop to fill zeros, swap the current non-zero element with the element at the insertion pointer. This naturally pushes zeros to the end.

Steps

• Initialize a pointer lastNonZeroFoundAt to 0.
• Iterate through the array with index i.
• If nums[i] is not 0, swap nums[i] with nums[lastNonZeroFoundAt] and increment lastNonZeroFoundAt.

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

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimal solution. It performs the operation in a single pass (though swapping might technically be more writes than the overwrite method, it minimizes loops).