Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Move Zeroes

EASYProblemSolveExternal Links

Description

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

You must do this in-place without making a copy of the array.

Follow up: Could you minimize the total number of operations done?

Examples

Example 1

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

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

Explanation: The non-zero elements 1, 3, and 12 maintain their original left-to-right order and are moved to the front. The two zeros are placed at the end.

Example 2

Input: nums = [0]

Output: [0]

Explanation: The array has only one element which is already 0. No changes are needed.

Constraints

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

Editorial

Brute Force — Using a Temporary Array

Intuition

The simplest way to think about this problem is: "What if I just picked out all the non-zero elements, lined them up, and then filled the rest with zeros?"

Imagine you have a row of boxes, some containing items and some empty (zero). You walk along the row, take out every item you find and place it on a new shelf in the same order. Once you've collected all the items, you fill the remaining spots on the shelf with empty boxes.

This is straightforward but requires creating a whole new array (the "shelf"), which costs extra memory. The problem asks us to do it in-place, so this approach doesn't fully satisfy the constraints — but it's the foundation for understanding the better approaches.

Step-by-Step Explanation

Let's trace through with nums = [0, 1, 0, 3, 12]:

Step 1: Create a temporary array of the same size, and a pointer j = 0 to track where to place the next non-zero element.

  • temp = [_, _, _, _, _], j = 0

Step 2: Scan index 0: nums[0] = 0. It's zero, skip it.

  • temp = [_, _, _, _, _], j = 0

Step 3: Scan index 1: nums[1] = 1. Non-zero! Place it at temp[j] = temp[0].

  • temp = [1, _, _, _, _], j = 1

Step 4: Scan index 2: nums[2] = 0. Zero, skip.

  • temp = [1, _, _, _, _], j = 1

Step 5: Scan index 3: nums[3] = 3. Non-zero! Place at temp[1].

  • temp = [1, 3, _, _, _], j = 2

Step 6: Scan index 4: nums[4] = 12. Non-zero! Place at temp[2].

  • temp = [1, 3, 12, _, _], j = 3

Step 7: Fill the remaining positions (indices 3 and 4) with 0.

  • temp = [1, 3, 12, 0, 0]

Step 8: Copy temp back into nums.

  • nums = [1, 3, 12, 0, 0]

Brute Force — Collect Non-Zeros into Temp Array, Fill Remaining with 0 — Watch as we scan the original array, copy non-zero elements to a temporary array, and fill the rest with zeros.

Algorithm

  1. Create a temporary array temp of size n
  2. Initialize pointer j = 0
  3. For each element in nums:
    • If it is non-zero, copy it to temp[j] and increment j
  4. Fill positions j through n-1 in temp with 0
  5. Copy temp back into nums

Code

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        vector<int> temp(n, 0);
        int j = 0;
        
        // Copy non-zero elements
        for (int i = 0; i < n; i++) {
            if (nums[i] != 0) {
                temp[j++] = nums[i];
            }
        }
        
        // Copy back to nums
        for (int i = 0; i < n; i++) {
            nums[i] = temp[i];
        }
    }
};
class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        n = len(nums)
        temp = [0] * n
        j = 0
        
        # Copy non-zero elements
        for i in range(n):
            if nums[i] != 0:
                temp[j] = nums[i]
                j += 1
        
        # Copy back to nums
        for i in range(n):
            nums[i] = temp[i]
class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int[] temp = new int[n];
        int j = 0;
        
        // Copy non-zero elements
        for (int i = 0; i < n; i++) {
            if (nums[i] != 0) {
                temp[j++] = nums[i];
            }
        }
        
        // Copy back to nums
        for (int i = 0; i < n; i++) {
            nums[i] = temp[i];
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the array twice — once to copy non-zero elements and once to copy temp back. Both are O(n), giving O(2n) = O(n) overall.

Space Complexity: O(n)

We create a temporary array of the same size as the input. This violates the in-place constraint but illustrates the core idea that better approaches build upon.

Why This Approach Is Not Efficient

The brute force approach uses O(n) extra space for the temporary array, directly violating the problem's in-place requirement. Beyond that, it also copies data unnecessarily — every element gets written twice (once to temp, once back to nums).

The key insight to eliminate extra space is: we don't need a separate array because we can use the beginning of the original array itself as the "temp" space. Think about it — as we scan left to right and encounter non-zero elements, the positions behind our scan pointer are either already processed or contain values we've already moved. We can overwrite them safely.

This leads to the "Two Traversals" approach: in the first pass, we shift all non-zero elements to the front (overwriting as we go), and in the second pass, we fill the remaining positions with zeros. This achieves O(1) space.

But can we do even better? Yes — by using swaps instead of overwrites, we can accomplish everything in a single traversal. When we find a non-zero element, we swap it with the position where it should go. This naturally pushes zeros to the end without a second pass.

Better Approach — Two Traversals (Overwrite)

Intuition

Instead of using a separate temporary array, we use the front of the original array itself as the destination for non-zero elements.

Imagine you're organizing a bookshelf. You walk along and push every real book (non-zero) to the left, stacking them tightly. Once all books are pushed left, you know exactly how many empty slots remain at the right end — just fill those with zeros.

We maintain a pointer count that tells us: "the next non-zero element should go here." As we scan with i, whenever we find a non-zero element, we write it at arr[count] and advance count. After the scan, everything from count to n-1 should be zeros.

Step-by-Step Explanation

Let's trace through with nums = [0, 1, 0, 3, 12]:

Step 1: Initialize count = 0. Start scanning.

Step 2: i = 0: nums[0] = 0. Zero — skip. count stays 0.

Step 3: i = 1: nums[1] = 1. Non-zero! Write nums[count] = nums[0] = 1. Increment count to 1.

  • Array: [1, 1, 0, 3, 12]

Step 4: i = 2: nums[2] = 0. Zero — skip. count stays 1.

Step 5: i = 3: nums[3] = 3. Non-zero! Write nums[count] = nums[1] = 3. Increment count to 2.

  • Array: [1, 3, 0, 3, 12]

Step 6: i = 4: nums[4] = 12. Non-zero! Write nums[count] = nums[2] = 12. Increment count to 3.

  • Array: [1, 3, 12, 3, 12]

Step 7: Second pass — fill indices 3 and 4 with 0.

  • Array: [1, 3, 12, 0, 0]

Done! No extra array needed.

Two Traversals — Shift Non-Zeros Left, Then Fill Zeros — Watch the first pass shift all non-zero elements to the front in order, then the second pass fills the tail with zeros. No extra space needed.

Algorithm

  1. Initialize count = 0
  2. First traversal: For each element nums[i]:
    • If nums[i] != 0, set nums[count] = nums[i] and increment count
  3. Second traversal: For each index from count to n-1:
    • Set nums[index] = 0

Code

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int count = 0;
        
        // First pass: shift non-zero elements to front
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                nums[count++] = nums[i];
            }
        }
        
        // Second pass: fill remaining with zeros
        while (count < nums.size()) {
            nums[count++] = 0;
        }
    }
};
class Solution:
    def moveZeroes(self, nums: list[int]) -> None:
        count = 0
        
        # First pass: shift non-zero elements to front
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[count] = nums[i]
                count += 1
        
        # Second pass: fill remaining with zeros
        while count < len(nums):
            nums[count] = 0
            count += 1
class Solution {
    public void moveZeroes(int[] nums) {
        int count = 0;
        
        // First pass: shift non-zero elements to front
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[count++] = nums[i];
            }
        }
        
        // Second pass: fill remaining with zeros
        while (count < nums.length) {
            nums[count++] = 0;
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

Two passes through the array — one for shifting non-zero elements and one for filling zeros. Total: O(n) + O(n) = O(n).

Space Complexity: O(1)

All operations are done in-place. Only a single integer variable count is used. No extra data structures are created.

Why This Approach Is Not Efficient

While the two-traversal approach achieves O(n) time and O(1) space, it has a subtle inefficiency: it always writes every element at least once, even when no movement is needed. Consider an array like [1, 2, 3, 0, 0] — the first three elements don't need to move at all, but the overwrite approach still writes them to the same positions.

More importantly, it requires two separate passes. The first pass doesn't know about the zeros it's leaving behind, so a second pass is needed to clean up.

The optimal approach uses swapping instead of overwriting. When we encounter a non-zero element, we swap it with the element at the count position. This has two advantages:

  1. Single traversal — everything happens in one pass
  2. Minimal writes — if i == count (no zero has been seen yet), the swap is a no-op. Elements only move when they actually need to

The swap naturally moves zeros rightward and non-zeros leftward in a single elegant pass.

Optimal Approach — Two Pointers with Swap (Single Traversal)

Intuition

Think of two pointers moving through the array:

  • i (the explorer): walks through every element, one by one
  • j (the placer): points to where the next non-zero element should be placed

The invariant is: everything before j is finalized (all non-zero, in the correct order), and everything between j and i is zeros.

When i finds a non-zero element, it swaps it with whatever is at position j. Since everything between j and i is zeros, this swap moves the non-zero element to its correct position and pushes a zero further right. Then j advances.

When i finds a zero, it just moves on — the zero is already in the "zero zone" between j and i.

This is essentially a partition operation: we're partitioning the array into [non-zeros | zeros], and we're doing it stably (maintaining relative order of non-zeros).

Step-by-Step Explanation

Let's trace through with nums = [0, 1, 0, 3, 12]:

Step 1: Initialize j = 0. Start scanning with i = 0.

Step 2: i = 0: nums[0] = 0. It's zero, do nothing. j stays at 0.

  • Array: [0, 1, 0, 3, 12]

Step 3: i = 1: nums[1] = 1. Non-zero! Swap nums[1] with nums[j] = nums[0].

  • Swap positions 0 and 1: [0, 1] → [1, 0]
  • Array: [1, 0, 0, 3, 12]. Advance j to 1.

Step 4: i = 2: nums[2] = 0. Zero, skip. j stays at 1.

  • Array: [1, 0, 0, 3, 12]

Step 5: i = 3: nums[3] = 3. Non-zero! Swap nums[3] with nums[j] = nums[1].

  • Swap positions 1 and 3: [0, 3] → [3, 0]
  • Array: [1, 3, 0, 0, 12]. Advance j to 2.

Step 6: i = 4: nums[4] = 12. Non-zero! Swap nums[4] with nums[j] = nums[2].

  • Swap positions 2 and 4: [0, 12] → [12, 0]
  • Array: [1, 3, 12, 0, 0]. Advance j to 3.

Step 7: i has finished scanning. The array is [1, 3, 12, 0, 0]. All done in a single pass!

Optimal — Two Pointers with Swap in a Single Pass — Watch how the explorer pointer i scans every element while the placer pointer j marks where the next non-zero should go. Each swap moves a non-zero into position and pushes a zero right.

Algorithm

  1. Initialize pointer j = 0 (marks the position for the next non-zero)
  2. For each index i from 0 to n-1:
    • If nums[i] != 0:
      • Swap nums[i] with nums[j]
      • Increment j
  3. After the loop, the array is fully partitioned: [non-zeros | zeros]

Code

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int j = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                swap(nums[i], nums[j]);
                j++;
            }
        }
    }
};
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
class Solution {
    public void moveZeroes(int[] nums) {
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                j++;
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

A single traversal through the array. Each element is visited exactly once by pointer i. The swap operation at each step is O(1). Total: O(n).

Space Complexity: O(1)

Only two integer variables (i and j) are used regardless of input size. All modifications are done in-place through swaps — no extra data structures.