Move Zeroes

LeetCode 283: Move Zeroes Solution & Explanation

Problem Overview

TL;DR: Use a "write pointer" to consolidate all non-zero elements at the beginning of the array, then fill the remaining positions with zeros (or swap elements to achieve the same effect in one pass).

The LeetCode 283 problem, titled Move Zeroes, asks us to manipulate an integer array nums. The objective is to shift all occurrences of 0 to the end of the array. Crucially, the relative order of the non-zero elements must remain unchanged. This operation must be performed in-place, meaning we cannot allocate a new array to store the result; we must modify the input array directly with $O(1)$ extra space.

Brute Force Approach for Move Zeroes

A naive approach to solving Move Zeroes usually involves prioritizing the logic over the space constraints. One might attempt to create a temporary array to store the result.

Naive Algorithm:

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:

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$).

Algorithm Strategy: Two Pointer Patterns

1. Initialization: Initialize a variable write_pointer (often called lastNonZeroFoundAt) to 0. This tracks the position where the next non-zero value should be written.
2. Iteration: Start a loop with a variable read_pointer (usually the loop index i) iterating from 0 to the end of the array.
3. Condition Check: Inside the loop, check if nums[read_pointer] is non-zero.
4. Swap and Advance:
   • If nums[read_pointer] is non-zero, swap the values at nums[write_pointer] and nums[read_pointer].
   • Increment write_pointer.
   • (If nums[read_pointer] is zero, do nothing; just let the read_pointer continue).
5. Completion: Once the read_pointer finishes the array, all non-zeros are compacted at the start, and all zeros have been implicitly moved to the end via the swaps.

Note: An alternative implementation is to copy non-zeros to write_pointer and then fill the remaining indices with 0 in a separate loop. The swap method is generally preferred as it handles the "minimize operations" follow-up more elegantly.

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.

Pattern Reuse Notes

The Two Pointers - In-place Array Modification pattern is a fundamental technique for array manipulation. Understanding the logic of write_pointer vs read_pointer enables you to solve several related interview questions efficiently:

• LeetCode 26: Remove Duplicates from Sorted Array - Uses the exact same logic, but the condition checks for uniqueness rather than non-zero values.
• LeetCode 27: Remove Element - Identical structure; instead of moving zeros, you overwrite a specific target value.
• LeetCode 75: Sort Colors - A more complex variation involving three pointers (low, mid, high) to sort 0s, 1s, and 2s in-place.
• LeetCode 80: Remove Duplicates from Sorted Array II - Extends the pattern to allow at most two duplicates, requiring slightly more complex pointer logic.

Reference Implementation

C++ Solution for LeetCode 283

1class Solution {
2public:
3    void moveZeroes(vector<int>& nums) {
4        int writePtr = 0;
5        
6        // Iterate through the array with a read pointer (i)
7        for (int readPtr = 0; readPtr < nums.size(); readPtr++) {
8            // If the current element is non-zero
9            if (nums[readPtr] != 0) {
10                // Swap the non-zero element to the write position
11                // This handles both moving non-zeros to front 
12                // and zeros to back simultaneously.
13                swap(nums[writePtr], nums[readPtr]);
14                writePtr++;
15            }
16        }
17    }
18};

Java Solution for LeetCode 283

1class Solution {
2    public void moveZeroes(int[] nums) {
3        int writePtr = 0;
4        
5        // Iterate through the array
6        for (int readPtr = 0; readPtr < nums.length; readPtr++) {
7            // If we find a non-zero element
8            if (nums[readPtr] != 0) {
9                // Swap the current element with the element at writePtr
10                int temp = nums[writePtr];
11                nums[writePtr] = nums[readPtr];
12                nums[readPtr] = temp;
13                
14                // Advance the write pointer
15                writePtr++;
16            }
17        }
18    }
19}

Python Solution for LeetCode 283

1class Solution:
2    def moveZeroes(self, nums: List[int]) -> None:
3        """
4        Do not return anything, modify nums in-place instead.
5        """
6        write_ptr = 0
7        
8        for read_ptr in range(len(nums)):
9            if nums[read_ptr] != 0:
10                # Pythonic swap to move non-zero to the front
11                nums[write_ptr], nums[read_ptr] = nums[read_ptr], nums[write_ptr]
12                write_ptr += 1