Move All Zeros to the End

Move all zeros in an array to the end while maintaining the relative order of non-zero elements

Language Selection

Choose your preferred programming language

Showing: Python

Move All Zeros to the End

Problem Statement

Given an integer array nums, move all zeros to the end of the array while maintaining the relative order of the non-zero elements. The operation must be done in-place without making a copy of the array.

Input/Output Specifications

Input: An array of integers nums where 0 <= nums.length <= 10^4 and -2^31 <= nums[i] <= 2^31 - 1
Output: The same array with all zeros moved to the end (modified in-place)

Constraints

Must modify the array in-place
Maintain relative order of non-zero elements
Minimize the number of operations performed on the array
The array can contain positive, negative, and zero integers

Examples

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Explanation: Non-zero elements [1,3,12] maintain their order, zeros moved to end.

Example 2:

Input: nums = [0]
Output: [0]
Explanation: Single zero element stays in place.

Example 3:

Input: nums = [1,2,3]
Output: [1,2,3]
Explanation: No zeros to move, array remains unchanged.

Example 4:

Input: nums = [0,0,1]
Output: [1,0,0]
Explanation: Single non-zero element moves to front, zeros to end.

Solution Approaches

Approach 1: Two Pointers (Optimal)

Algorithm Explanation:

Use two pointers: one for the current position and one for the next non-zero position
The left pointer tracks where the next non-zero element should be placed
The right pointer scans through the array looking for non-zero elements
When a non-zero element is found, place it at the left pointer position
After processing all elements, fill remaining positions with zeros

Implementation:

Python:

def move_zeros_to_end(nums):
    """
    Move zeros to end using two pointers approach
    Time: O(n)
    Space: O(1)
    """
    if not nums:
        return
    
    # Pointer for next non-zero element position
    left = 0
    
    # Move all non-zero elements to the front
    for right in range(len(nums)):
        if nums[right] != 0:
            nums[left] = nums[right]
            left += 1
    
    # Fill remaining positions with zeros
    while left < len(nums):
        nums[left] = 0
        left += 1

# Alternative with swapping (preserves exact positions)
def move_zeros_swap(nums):
    """
    Move zeros to end using swapping approach
    Time: O(n)
    Space: O(1)
    """
    if not nums:
        return
    
    left = 0  # Position for next non-zero element
    
    for right in range(len(nums)):
        if nums[right] != 0:
            # Swap non-zero element to front
            nums[left], nums[right] = nums[right], nums[left]
            left += 1

# Alternative using list operations (not in-place)
def move_zeros_new_list(nums):
    """
    Move zeros using new list creation
    Time: O(n)
    Space: O(n)
    """
    non_zeros = [num for num in nums if num != 0]
    zeros = [0] * (len(nums) - len(non_zeros))
    return non_zeros + zeros

Java:

class Solution {
    /**
     * Move zeros to end using two pointers approach
     * Time: O(n)
     * Space: O(1)
     */
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        
        int left = 0;  // Position for next non-zero element
        
        // Move all non-zero elements to the front
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != 0) {
                nums[left] = nums[right];
                left++;
            }
        }
        
        // Fill remaining positions with zeros
        while (left < nums.length) {
            nums[left] = 0;
            left++;
        }
    }
    
    // Alternative with swapping
    public void moveZeroesSwap(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        
        int left = 0;  // Position for next non-zero element
        
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != 0) {
                // Swap elements
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
            }
        }
    }
    
    // Using ArrayList (not in-place)
    public int[] moveZeroesList(int[] nums) {
        if (nums == null) return nums;
        
        List<Integer> nonZeros = new ArrayList<>();
        int zeroCount = 0;
        
        for (int num : nums) {
            if (num != 0) {
                nonZeros.add(num);
            } else {
                zeroCount++;
            }
        }
        
        // Add zeros to the end
        for (int i = 0; i < zeroCount; i++) {
            nonZeros.add(0);
        }
        
        return nonZeros.stream().mapToInt(i -> i).toArray();
    }
}

Go:

// moveZerosToEnd - Move zeros to end using two pointers approach
// Time: O(n)
// Space: O(1)
func moveZerosToEnd(nums []int) {
    if len(nums) <= 1 {
        return
    }
    
    left := 0  // Position for next non-zero element
    
    // Move all non-zero elements to the front
    for right := 0; right < len(nums); right++ {
        if nums[right] != 0 {
            nums[left] = nums[right]
            left++
        }
    }
    
    // Fill remaining positions with zeros
    for left < len(nums) {
        nums[left] = 0
        left++
    }
}

// Alternative with swapping
func moveZerosSwap(nums []int) {
    if len(nums) <= 1 {
        return
    }
    
    left := 0  // Position for next non-zero element
    
    for right := 0; right < len(nums); right++ {
        if nums[right] != 0 {
            // Swap elements
            nums[left], nums[right] = nums[right], nums[left]
            left++
        }
    }
}

// Creating new slice (not in-place)
func moveZerosNewSlice(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }
    
    var nonZeros []int
    zeroCount := 0
    
    for _, num := range nums {
        if num != 0 {
            nonZeros = append(nonZeros, num)
        } else {
            zeroCount++
        }
    }
    
    // Add zeros to the end
    for i := 0; i < zeroCount; i++ {
        nonZeros = append(nonZeros, 0)
    }
    
    return nonZeros
}

JavaScript:

/**
 * Move zeros to end using two pointers approach
 * Time: O(n)
 * Space: O(1)
 */
function moveZeroes(nums) {
    if (!nums || nums.length <= 1) {
        return;
    }
    
    let left = 0;  // Position for next non-zero element
    
    // Move all non-zero elements to the front
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] !== 0) {
            nums[left] = nums[right];
            left++;
        }
    }
    
    // Fill remaining positions with zeros
    while (left < nums.length) {
        nums[left] = 0;
        left++;
    }
}

// Alternative with swapping
function moveZeroesSwap(nums) {
    if (!nums || nums.length <= 1) {
        return;
    }
    
    let left = 0;  // Position for next non-zero element
    
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] !== 0) {
            // Swap elements
            [nums[left], nums[right]] = [nums[right], nums[left]];
            left++;
        }
    }
}

// Using filter and fill (functional approach)
function moveZeroesFilter(nums) {
    if (!nums || nums.length <= 1) {
        return nums;
    }
    
    const nonZeros = nums.filter(num => num !== 0);
    const zeros = new Array(nums.length - nonZeros.length).fill(0);
    
    return [...nonZeros, ...zeros];
}

// Alternative using splice (modifies original array)
function moveZeroesSplice(nums) {
    if (!nums || nums.length <= 1) {
        return;
    }
    
    let i = 0;
    while (i < nums.length) {
        if (nums[i] === 0) {
            // Remove zero and add it to the end
            nums.push(nums.splice(i, 1)[0]);
        } else {
            i++;
        }
    }
}

C#:

public class Solution {
    /// <summary>
    /// Move zeros to end using two pointers approach
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public void MoveZeroes(int[] nums) {
        if (nums == null || nums.Length <= 1) {
            return;
        }
        
        int left = 0;  // Position for next non-zero element
        
        // Move all non-zero elements to the front
        for (int right = 0; right < nums.Length; right++) {
            if (nums[right] != 0) {
                nums[left] = nums[right];
                left++;
            }
        }
        
        // Fill remaining positions with zeros
        while (left < nums.Length) {
            nums[left] = 0;
            left++;
        }
    }
    
    // Alternative with swapping
    public void MoveZeroesSwap(int[] nums) {
        if (nums == null || nums.Length <= 1) {
            return;
        }
        
        int left = 0;  // Position for next non-zero element
        
        for (int right = 0; right < nums.Length; right++) {
            if (nums[right] != 0) {
                // Swap elements
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
            }
        }
    }
    
    // Using LINQ (creates new array)
    public int[] MoveZeroesLinq(int[] nums) {
        if (nums == null) return nums;
        
        var nonZeros = nums.Where(x => x != 0).ToArray();
        var zeros = new int[nums.Length - nonZeros.Length];
        
        return nonZeros.Concat(zeros).ToArray();
    }
}

Complexity Analysis:

Time Complexity: O(n) - We traverse the array once
Space Complexity: O(1) - Only using a constant amount of extra space

Trade-offs:

Optimal time and space complexity
Maintains relative order of non-zero elements
Simple two-pointer technique
In-place modification

Approach 2: Bubble Sort Style (Brute Force)

Algorithm Explanation:

For each zero found, bubble it to the end of the array
Swap adjacent elements to move zero towards the end
Continue until all zeros are at the end
This approach is less efficient but demonstrates the concept

Implementation:

Python:

def move_zeros_bubble(nums):
    """
    Move zeros to end using bubble sort approach
    Time: O(n²)
    Space: O(1)
    """
    if not nums:
        return
    
    n = len(nums)
    
    for i in range(n):
        for j in range(n - 1):
            # If current element is 0 and next is non-zero, swap
            if nums[j] == 0 and nums[j + 1] != 0:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]

Java:

class Solution {
    /**
     * Move zeros to end using bubble sort approach
     * Time: O(n²)
     * Space: O(1)
     */
    public void moveZeroesBubble(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        
        int n = nums.length;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {
                // If current element is 0 and next is non-zero, swap
                if (nums[j] == 0 && nums[j + 1] != 0) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }
}

Go:

// moveZerosBubble - Move zeros using bubble sort approach
// Time: O(n²)
// Space: O(1)
func moveZerosBubble(nums []int) {
    if len(nums) <= 1 {
        return
    }
    
    n := len(nums)
    
    for i := 0; i < n; i++ {
        for j := 0; j < n-1; j++ {
            // If current element is 0 and next is non-zero, swap
            if nums[j] == 0 && nums[j+1] != 0 {
                nums[j], nums[j+1] = nums[j+1], nums[j]
            }
        }
    }
}

JavaScript:

/**
 * Move zeros to end using bubble sort approach
 * Time: O(n²)
 * Space: O(1)
 */
function moveZeroesBubble(nums) {
    if (!nums || nums.length <= 1) {
        return;
    }
    
    const n = nums.length;
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n - 1; j++) {
            // If current element is 0 and next is non-zero, swap
            if (nums[j] === 0 && nums[j + 1] !== 0) {
                [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
            }
        }
    }
}

C#:

public class Solution {
    /// <summary>
    /// Move zeros to end using bubble sort approach
    /// Time: O(n²)
    /// Space: O(1)
    /// </summary>
    public void MoveZeroesBubble(int[] nums) {
        if (nums == null || nums.Length <= 1) {
            return;
        }
        
        int n = nums.Length;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {
                // If current element is 0 and next is non-zero, swap
                if (nums[j] == 0 && nums[j + 1] != 0) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }
}

Complexity Analysis:

Time Complexity: O(n²) - Nested loops for bubble sort approach
Space Complexity: O(1) - Only using a constant amount of extra space

Trade-offs:

Simple logic but inefficient
Many unnecessary swaps
Good for understanding the movement concept
Not recommended for production use

Key Insights

Two Pointers Technique: Efficiently partitions array into non-zero and zero sections
Stable Partitioning: Maintains relative order of non-zero elements
In-Place Operations: Achieves O(1) space complexity through careful pointer management
Write vs Swap: Writing approach is slightly more efficient than swapping

Edge Cases

Empty Array: [] → Remains []
No Zeros: [1,2,3] → Remains [1,2,3]
All Zeros: [0,0,0] → Remains [0,0,0]
Single Zero: [0] → Remains [0]
Single Non-Zero: [5] → Remains [5]
Alternating: [0,1,0,1] → Becomes [1,1,0,0]
Zeros at Start: [0,0,1,2] → Becomes [1,2,0,0]
Zeros at End: [1,2,0,0] → Remains [1,2,0,0]

How Solutions Handle Edge Cases:

Length checks prevent unnecessary processing
Two-pointer logic works correctly for all distributions
Proper handling of boundary conditions
Maintains array integrity in all cases

Test Cases

def test_move_zeros():
    # Basic case
    nums = [0,1,0,3,12]
    move_zeros_to_end(nums)
    assert nums == [1,3,12,0,0]
    
    # Single zero
    nums = [0]
    move_zeros_to_end(nums)
    assert nums == [0]
    
    # No zeros
    nums = [1,2,3]
    move_zeros_to_end(nums)
    assert nums == [1,2,3]
    
    # All zeros
    nums = [0,0,0]
    move_zeros_to_end(nums)
    assert nums == [0,0,0]
    
    # Zeros at start
    nums = [0,0,1]
    move_zeros_to_end(nums)
    assert nums == [1,0,0]
    
    # Zeros at end
    nums = [1,2,0,0]
    move_zeros_to_end(nums)
    assert nums == [1,2,0,0]
    
    # Alternating
    nums = [0,1,0,1,0]
    move_zeros_to_end(nums)
    assert nums == [1,1,0,0,0]
    
    # Mixed with negatives
    nums = [0,-1,0,3,-12]
    move_zeros_to_end(nums)
    assert nums == [-1,3,-12,0,0]
    
    print("All tests passed!")

test_move_zeros()

Follow-up Questions

Move Specific Value: How would you move all instances of a specific value to the end?
Move to Beginning: How would you move zeros to the beginning instead?
Count Operations: What’s the minimum number of swaps needed?
Multiple Values: How would you move multiple specific values to the end?
Linked List: How would you solve this for a linked list?

Common Mistakes

Not Maintaining Order: Disrupting the relative order of non-zero elements
- Problem: Using simple sorting which doesn’t preserve order
- Solution: Use stable partitioning with two pointers
Unnecessary Swaps: Swapping when elements are already in correct position
- Problem: Extra operations and potential bugs
- Solution: Check if swap is needed before performing it
Index Out of Bounds: Incorrect pointer management
- Problem: Accessing invalid array indices
- Solution: Proper boundary checks in loops
Forgetting to Fill Zeros: Not filling the end positions with zeros
- Problem: Array may contain garbage values at the end
- Solution: Explicitly set remaining positions to zero

Interview Tips

Clarify Requirements: Confirm in-place requirement and order preservation
Start with Brute Force: Mention bubble sort approach, then optimize
Use Two Pointers: This is the optimal approach for this problem
Discuss Variants: Mention writing vs swapping implementations
Test Edge Cases: Walk through arrays with no zeros, all zeros, etc.

Concept Explanations

Array Partitioning: This problem demonstrates stable partitioning, where elements are separated based on a condition while maintaining their relative order within each partition.

Two Pointers for Partitioning: The technique of using one pointer to track the partition boundary and another to scan elements is fundamental for many array problems.

When to Apply: Use this pattern for problems involving moving elements based on conditions, such as moving even/odd numbers, positive/negative values, or any boolean predicate.