#283

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Move Zeroes

Move all zeros in an array to the end while preserving the order of non-zero elements using efficient in-place operations.

array two pointers

Problem Statement

Given an integer array nums, rearrange the elements so that all 0's are moved to the end while keeping the relative order of non-zero elements intact. You must solve this without allocating extra arrays, performing all modifications directly on the input array.

For example, given nums = [0,1,0,3,12], the result should be [1,3,12,0,0]. Constraints are 1 <= nums.length <= 10^4 and -2^31 <= nums[i] <= 2^31 - 1.

Examples

Example 1

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

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

Example details omitted.

Example 2

Input: nums = [0]

Output: [0]

Example details omitted.

Constraints

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

Solution Approach

Two-pointer scan with swap

Use a 'lastNonZeroFoundAt' pointer to track where the next non-zero should go. Iterate through the array with a scanning pointer, swapping non-zero elements to the 'lastNonZeroFoundAt' position and incrementing it. This preserves relative order and accumulates zeros at the end efficiently.

Overwrite then fill zeros

First, overwrite the array by moving all non-zero elements to the front using a scanning pointer. After placing all non-zeros, fill the remaining positions with zeros. This method reduces unnecessary swaps while adhering strictly to the in-place constraint.

Minimal swap optimization

Only swap when the scanning pointer finds a non-zero element that is not already at the 'lastNonZeroFoundAt' index. This reduces redundant operations and handles arrays with many zeros efficiently, aligning with the common interview pattern for two-pointer invariant tracking.

Complexity Analysis

Metric	Value
Time	O(n)
Space	Depends on the final approach

Time complexity is O(n) since each element is visited at most once. Space complexity is O(1) because the rearrangement occurs in-place without additional arrays.

What Interviewers Usually Probe

Watch for attempts to create a copy of the array instead of in-place rearrangement.
Check if candidates maintain the relative order of non-zero elements while moving zeros.
Look for correct use of a two-pointer invariant to minimize unnecessary swaps.

Common Pitfalls or Variants

Common pitfalls

Swapping elements unnecessarily even when non-zero is already in place.
Failing to handle arrays where all elements are zeros or all non-zeros.
Using extra memory instead of modifying the input array directly.

Follow-up variants

Move all occurrences of a specific number to the end while preserving order.
Partition an array into even and odd numbers using a similar two-pointer approach.
Move zeros to the beginning instead of the end while keeping non-zero order.

FAQ

What is the main pattern used in Move Zeroes?

The primary pattern is two-pointer scanning with invariant tracking, where one pointer scans and the other tracks the next position for non-zero elements.

Do I need extra space to solve Move Zeroes?

No, the problem must be solved in-place, modifying the input array without allocating additional arrays.

Can I swap zeros with non-zeros multiple times?

Minimize swaps by only moving non-zero elements when they are not already in the correct position, ensuring efficiency.

How does GhostInterview verify Move Zeroes solutions?

It simulates each step of your two-pointer approach, showing the state of the array after every move to catch ordering mistakes.

What are common mistakes when solving Move Zeroes?

Creating extra arrays, ignoring relative order of non-zero elements, or performing unnecessary swaps with zeros are frequent errors.

terminal

Solution

Solution 1: Two Pointers

We use a pointer $k$ to record the current position to insert, initially $k = 0$.

1

2

3

4

5

6

7

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        k = 0
        for i, x in enumerate(nums):
            if x:
                nums[k], nums[i] = nums[i], nums[k]
                k += 1

Continue Practicing

#287 find the duplicate number #321 create maximum number #349 intersection of two arrays