Code Implementation

class Solution:
    def moveZeroes(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        """
        insert_pos = 0
        for num in nums:
            if num != 0:
                nums[insert_pos] = num
                insert_pos += 1
        for i in range(insert_pos, len(nums)):
            nums[i] = 0
      

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int insertPos = 0;
        for (int num : nums) {
            if (num != 0) {
                nums[insertPos++] = num;
            }
        }
        for (int i = insertPos; i < nums.size(); ++i) {
            nums[i] = 0;
        }
    }
};
      

class Solution {
    public void moveZeroes(int[] nums) {
        int insertPos = 0;
        for (int num : nums) {
            if (num != 0) {
                nums[insertPos++] = num;
            }
        }
        while (insertPos < nums.length) {
            nums[insertPos++] = 0;
        }
    }
}
      

var moveZeroes = function(nums) {
    let insertPos = 0;
    for (let num of nums) {
        if (num !== 0) {
            nums[insertPos++] = num;
        }
    }
    while (insertPos < nums.length) {
        nums[insertPos++] = 0;
    }
};
      

Problem Description

You are given an array of integers nums. Your task is to move all the zeros in the array to the end, while maintaining the relative order of the non-zero elements. This operation must be done in-place (i.e., without making a copy of the array), and you should minimize the total number of operations.

• Modify the input array nums directly.
• Keep the order of non-zero elements the same as in the original array.
• All zeros should appear at the end of the array.
• Try to achieve this with minimal extra space (ideally O(1)).

Thought Process

At first glance, you might think about creating a new array and copying over all the non-zero elements, then filling the rest with zeros. However, the problem specifically asks for an in-place solution, so we can't use extra arrays.

The brute-force way would be to repeatedly scan the array and swap zeros with the next non-zero element. But this approach is inefficient and could require many unnecessary operations.

To optimize, we want to minimize writes and only move each element at most once. A good way to do this is to use a "write pointer" or "insert position" that keeps track of where the next non-zero element should go. This way, we can process the array in a single pass and handle all the moves efficiently.

Solution Approach

Let's break down the optimal approach step by step:

1. Initialize a pointer: Start with a variable (let's call it insertPos) set to 0. This will keep track of where the next non-zero element should be placed.
2. First pass - move non-zeros forward: Iterate through the array. For each non-zero element, assign it to nums[insertPos], then increment insertPos. This effectively "compacts" all non-zero elements at the front of the array, in order.
3. Second pass - fill zeros: After all non-zero elements have been moved, fill the rest of the array (from insertPos to the end) with zeros.

This approach ensures that:

• All non-zero elements retain their original order.
• All zeros are moved to the end.
• We only traverse the array twice (or once, if you do both steps together).
• No extra space is required beyond a few variables.

Example Walkthrough

Let's work through an example with nums = [0, 1, 0, 3, 12]:

1. Initial State: [0, 1, 0, 3, 12], insertPos = 0
2. First Pass:
   • Index 0: 0 (skip, since it's zero)
   • Index 1: 1 (non-zero, set nums[0] = 1, insertPos = 1)
   • Index 2: 0 (skip)
   • Index 3: 3 (non-zero, set nums[1] = 3, insertPos = 2)
   • Index 4: 12 (non-zero, set nums[2] = 12, insertPos = 3)

   Array after first pass: [1, 3, 12, 3, 12]

3. Second Pass:
   • Fill nums[3] and nums[4] with 0.

   Final array: [1, 3, 12, 0, 0]

Notice how the non-zero elements remain in their original order, and all zeros are moved to the end.

Time and Space Complexity

• Brute-force approach:
  • Time: O(n²), since you might shift elements multiple times for each zero.
  • Space: O(1), as long as you do it in-place.
• Optimized approach (two pointers):
  • Time: O(n), since you traverse the array at most twice (once for moving non-zeros, once for filling zeros).
  • Space: O(1), as only a few variables are used regardless of input size.

The optimized solution is both time and space efficient, making it suitable for large arrays.

Summary

The "Move Zeroes" problem is a classic example of in-place array manipulation. By using a two-pointer strategy, we efficiently move all non-zero elements forward and fill the remainder with zeros, all in a single pass plus a quick cleanup. This approach is both simple and optimal, showcasing how a little planning can lead to elegant and efficient code.