Move Zeroes

283.Move Zeroes

Array

Two Pointers

Problem Statement:

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.

Example:

Input:

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

→

Output:

[1,3,12,0,0]

Algorithm:

1. Use two pointers approach
2. Move non-zero elements to front
3. Fill remaining positions with zeros
4. Or use swap technique for one-pass

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

// Two-pass solution
public void moveZeroes(int[] nums) {
    int k = 0;  // Position for next non-zero element

    // First pass: place non-zero elements
    for (int i = 0; i < nums.length; i++) 
        if (nums[i] != 0) 
            nums[k++] = nums[i];

    // Second pass: fill remaining with zeros
    for (int i = k; i < nums.length; i++) 
        nums[i] = 0;
}

// One-pass solution using swap
public void moveZeroesSwap(int[] nums) {
    if (nums == null || nums.length == 0) 
        return;
    
    int cur = 0;  // Position for next non-zero element

    for (int i = 0; i < nums.length; ++i) {
        if (nums[i] != 0) {
            int temp = nums[cur];
            nums[cur++] = nums[i];
            nums[i] = temp;
        }
    }
}

Python Solution:

def moveZeroes(self, nums: List[int]) -> None:
    k = 0  # Position for next non-zero element
    
    # Move non-zero elements to front
    for i in range(len(nums)):
        if nums[i] != 0:
            nums[k] = nums[i]
            k += 1
            
    # Fill remaining with zeros
    for i in range(k, len(nums)):
        nums[i] = 0

C++ Solution:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int k = 0;  // Position for next non-zero element
        
        // Move non-zero elements to front
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] != 0) {
                swap(nums[k], nums[i]);
                k++;
            }
        }
    }
};