LeetCodee

283. Move Zeroes

Jump to Solution: Python Java C++ JavaScript C#

Problem 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.

Note that you must do this in-place without making a copy of the array.

Example 1:

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

Example 2:

Input: nums = [0]
Output: [0]

Constraints:

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

Follow up:

Could you minimize the total number of operations done?

Solution

Python Solution

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # Position for next non-zero element
        pos = 0
        
        # Move all non-zero elements to front
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[pos], nums[i] = nums[i], nums[pos]
                pos += 1

Time Complexity: O(n)

Single pass through the array.

Space Complexity: O(1)

In-place modification with constant extra space.

Java Solution

class Solution {
    public void moveZeroes(int[] nums) {
        // Position for next non-zero element
        int pos = 0;
        
        // Move all non-zero elements to front
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int temp = nums[pos];
                nums[pos] = nums[i];
                nums[i] = temp;
                pos++;
            }
        }
    }
}

Time Complexity: O(n)

Single pass through the array.

Space Complexity: O(1)

In-place modification with constant extra space.

C++ Solution

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

Time Complexity: O(n)

Single pass through the array.

Space Complexity: O(1)

In-place modification with constant extra space.

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    // Position for next non-zero element
    let pos = 0;
    
    // Move all non-zero elements to front
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== 0) {
            [nums[pos], nums[i]] = [nums[i], nums[pos]];
            pos++;
        }
    }
};

Time Complexity: O(n)

Single pass through the array.

Space Complexity: O(1)

In-place modification with constant extra space.

C# Solution

public class Solution {
    public void MoveZeroes(int[] nums) {
        // Position for next non-zero element
        int pos = 0;
        
        // Move all non-zero elements to front
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] != 0) {
                int temp = nums[pos];
                nums[pos] = nums[i];
                nums[i] = temp;
                pos++;
            }
        }
    }
}

Time Complexity: O(n)

Single pass through the array.

Space Complexity: O(1)

In-place modification with constant extra space.

Approach Explanation

The solution uses a two-pointer approach to move zeroes to the end:

  1. Key Insight:
    • Keep track of position for next non-zero element
    • Swap elements to maintain relative order
    • Single pass solution is possible
  2. Algorithm Steps:
    • Initialize position pointer to 0
    • Iterate through array
    • When non-zero found, swap with position
    • Increment position after swap

Example walkthrough for [0,1,0,3,12]:

  • Initial: [0,1,0,3,12], pos = 0
  • Find 1: [1,0,0,3,12], pos = 1
  • Find 3: [1,3,0,0,12], pos = 2
  • Find 12: [1,3,12,0,0], pos = 3

Optimization insights:

  • No need for extra array
  • Minimizes number of operations
  • Maintains stability of non-zero elements
  • Works in a single pass

Edge Cases:

  • Array with single element
  • Array with all zeros
  • Array with no zeros
  • Array with alternating zeros