1. Initialize a new empty array, result, of the same size as nums.
2. Iterate through nums. If an element is non-zero, append it to result.
3. Count the number of zeros encountered or simply fill the remaining slots in result with zeros after the loop.
4. Copy result back into nums.

Pseudo-code:

text
function moveZeroesNaive(nums):
    tempArray = []
    zeroCount = 0
    
    for x in nums:
        if x != 0:
            tempArray.append(x)
        else:
            zeroCount++
            
    while zeroCount > 0:
        tempArray.append(0)
        zeroCount--
        
    nums = tempArray // Copy back

Why this fails: While this solution produces the correct output, it violates the problem's strict constraint: "do this in-place without making a copy of the array."

• Time Complexity: $O(N)$, where $N$ is the number of elements.
• Space Complexity: $O(N)$ due to the temporary array. This makes the solution suboptimal for memory-constrained environments and invalid according to the problem statement.

Another brute force variation involves using nested loops (similar to Bubble Sort) to "bubble" zeros to the end one by one. This satisfies the space constraint but results in $O(N^2)$ time complexity, which is inefficient for large inputs ($N \le 10^4$).

Core Insight for Move Zeroes

The key intuition for the optimal LeetCode 283 Solution is to decouple the act of finding a non-zero element from the act of placing it.

We can maintain a pointer, let's call it write_pointer, that indicates the index where the next non-zero element belongs. As we iterate through the array with a read_pointer, every time we encounter a non-zero element, we know it belongs at the write_pointer's position.

The Invariant: At any step $i$ of the iteration, the subarray nums[0...write_pointer-1] contains all processed non-zero elements in their correct relative order.

By swapping the non-zero element found at read_pointer with the element at write_pointer, we achieve two things simultaneously:

1. The non-zero element moves to the "consolidated" section at the front.
2. The zero (if write_pointer was pointing to one) or the placeholder moves toward the end.

Visual Description: Imagine the array is divided into two logical regions by the write_pointer:

1. Stable Region (Left): Contains strictly non-zero elements in correct order.
2. Unexplored/Mixed Region (Right): Contains zeros and non-zeros that haven't been compacted yet.

As the read_pointer scans right, the write_pointer only advances when a non-zero is locked into the Stable Region. If the array has no zeros, both pointers move together. If zeros exist, the read_pointer moves ahead, creating a gap between the two pointers that represents the accumulated zeros.

Execution Flow

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

1. Start: write_pointer = 0, read_pointer = 0.
2. i = 0: nums[0] is 0.
   • Condition fail. write_pointer stays at 0.
3. i = 1: nums[1] is 1.
   • Condition pass (1 != 0).
   • Swap nums[write_pointer] (index 0) and nums[read_pointer] (index 1).
   • Array becomes [1, 0, 0, 3, 12].
   • Increment write_pointer to 1.
4. i = 2: nums[2] is 0.
   • Condition fail. write_pointer stays at 1.
5. i = 3: nums[3] is 3.
   • Condition pass (3 != 0).
   • Swap nums[1] (value 0) and nums[3] (value 3).
   • Array becomes [1, 3, 0, 0, 12].
   • Increment write_pointer to 2.
6. i = 4: nums[4] is 12.
   • Condition pass (12 != 0).
   • Swap nums[2] (value 0) and nums[4] (value 12).
   • Array becomes [1, 3, 12, 0, 0].
   • Increment write_pointer to 3.
7. End: Loop finishes. Result is [1, 3, 12, 0, 0].

Proof of Correctness

The algorithm is correct based on the Loop Invariant: At the start of each iteration i, the subarray nums[0...write_pointer-1] consists of all non-zero elements found in nums[0...i-1], in their original relative order.

1. Initialization: Before the loop, write_pointer is 0. The subarray is empty, vacuously satisfying the property.
2. Maintenance: When nums[i] is non-zero, we move it to nums[write_pointer]. Since write_pointer is the first available slot after the previously processed non-zeros, the relative order is preserved. We then increment write_pointer to maintain the invariant.
3. Termination: When i reaches $N$, nums[0...write_pointer-1] contains all non-zeros from the entire array. The remaining elements (from write_pointer to $N-1$) must be zeros because every time we found a non-zero, we moved it out of that area (via swap) or it was already in the correct place.

Reference Implementation

C++ Solution for LeetCode 283

cpp
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int writePtr = 0;
        
        // Iterate through the array with a read pointer (i)
        for (int readPtr = 0; readPtr < nums.size(); readPtr++) {
            // If the current element is non-zero
            if (nums[readPtr] != 0) {
                // Swap the non-zero element to the write position
                // This handles both moving non-zeros to front 
                // and zeros to back simultaneously.
                swap(nums[writePtr], nums[readPtr]);
                writePtr++;
            }
        }
    }
};

Java Solution for LeetCode 283

java
class Solution {
    public void moveZeroes(int[] nums) {
        int writePtr = 0;
        
        // Iterate through the array
        for (int readPtr = 0; readPtr < nums.length; readPtr++) {
            // If we find a non-zero element
            if (nums[readPtr] != 0) {
                // Swap the current element with the element at writePtr
                int temp = nums[writePtr];
                nums[writePtr] = nums[readPtr];
                nums[readPtr] = temp;
                
                // Advance the write pointer
                writePtr++;
            }
        }
    }
}

Python Solution for LeetCode 283

python
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        write_ptr = 0
        
        for read_ptr in range(len(nums)):
            if nums[read_ptr] != 0:
                # Pythonic swap to move non-zero to the front
                nums[write_ptr], nums[read_ptr] = nums[read_ptr], nums[write_ptr]
                write_ptr += 1