How do you solve Move Zeroes?

Iterate through the array with a right pointer. For each non-zero element, write it to the position indicated by the left pointer and increment the left pointer. After processing all elements, fill the rest of the array from the left pointer to the end with zeros. This approach guarantees O(n) time and O(1) auxiliary space.

What pattern does Move Zeroes use?

The Pattern: Two Pointers (Stable Partition) The Heuristic: Use one pointer to scan all elements and another to track the position to place the next valid element, enabling a stable partition of the array in a single pass without extra space.

Move Zeroes — Two Pointers

Q: What is the time complexity of Move Zeroes?

O(n). The algorithm makes a single pass through the array with the right pointer, and a second pass to fill zeros from the left pointer to the end, both linear operations.

Problem

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. This must be done in-place without making a copy of the array.

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

Example

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

Output: [1,3,12,0,0]

A naive approach might repeatedly swap zeros with the next non-zero element, resulting in many operations. Instead, the algorithm uses two pointers: one to scan through the array (right pointer) and one to track the position to place the next non-zero element (left pointer). As it iterates, it overwrites the left pointer's position with the current non-zero element and increments the left pointer. This effectively compacts all non-zero elements at the front in their original order.

Approach

Straightforward Solution

A brute-force approach swaps every zero with the next non-zero element found, which can lead to O(n^2) time complexity due to repeated swaps.

Core Observation

The relative order of non-zero elements must be preserved, and zeros must be moved to the end. This implies a stable partition of the array into non-zero and zero elements.

Path to Optimal

Preview

The key insight is to use two pointers: one scanning through the array and one marking the position to place the next non-zero element…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate through the array with a right pointer. For each non-zero element, write it to the position indicated by the left pointer and increment the left pointer…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm makes a single pass through the array with the right pointer, and a second pass to fill zeros from the left pointer to the end, both linear operations.

Space

O(1)

All operations are done in-place with only two integer pointers used, requiring constant auxiliary space.

Solution

Python

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

Step-by-Step Solution

1

Track Position to Place Next Non-Zero Element

3 l = 0

Objective

To maintain a pointer that marks the next index where a non-zero element should be placed.

Key Insight

The left pointer acts as a boundary between processed non-zero elements and the rest of the array. By incrementing it only when a non-zero element is found, the algorithm ensures that all non-zero elements are compacted at the front in their original order without gaps.

Interview Quick-Check

Core Logic

The left pointer tracks the position to overwrite with the next non-zero element, enabling stable compaction.

State & Boundaries

The left pointer starts at 0 and only moves forward when a non-zero element is placed, ensuring no overwriting of unprocessed elements.

Common Pitfalls & Bugs

Failing to increment the left pointer only on non-zero elements leads to incorrect overwriting and loss of order.

2

Iterate Through Array and Overwrite Non-Zero Elements

To scan the array with a right pointer and copy non-zero elements to the left pointer's position.

3

Fill Remaining Positions with Zeros

To overwrite the remaining elements from the left pointer to the end of the array with zeros.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 6 Critical

nums[l] = nums[r]

Overwrite the element at the left pointer with the current non-zero element.

We write the value found by the Read pointer into the compacted zone. Overwriting is preferred over swapping here because it reduces total memory operations (1 write vs 3 assignments).

Full line-by-line criticality + rationale for all 8 lines available on Pro.

Test Your Understanding

Why does overwriting elements at the left pointer with non-zero elements from the right pointer preserve the relative order of non-zero elements?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Move Zeroes from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Move Zeroes drill

or drill a free problem

1	`class Solution:`
2	`def moveZeroes(self, nums: List[int]) -> None:`
3	`l = 0`
4	`for r in range(len(nums)):`
5	`if nums[r] != 0:`
6	`nums[l] = nums[r]`
7	`l += 1`
8
9	`while l < len(nums):`
10	`nums[l] = 0`
11	`l += 1`