Move Zeroes Algorithm Solution

The move zeroes problem requires rearranging an array so all zeros appear at the end while preserving the order of non-zero elements. This classic coding interview question tests understanding of array manipulation and two-pointer techniques.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can we modify the input array in-place, or do we need to return a new array?
2. What are the constraints on input size (e.g., up to 10⁴ elements)?
3. Are duplicates allowed in the input array?
4. Should we preserve the relative order of non-zero elements?
5. What is the expected time complexity — O(n) or can we do better?

Restatement of the problem in my own words: The task is to rearrange an array of integers such that all zeros are moved to the end of the array while maintaining the relative order of all non-zero elements. The operation must be done in-place to optimize space usage.

Clarification of inputs, outputs, and constraints:

• Input: An integer array nums of length n (1 ≤ n ≤ 10⁴)
• Output: The same array with zeros moved to the end
• Constraints:
  • Must be done in-place (modify original array)
  • Relative order of non-zero elements must be preserved
  • Cannot use extra space for another array (except for a constant amount)
  • Array can contain negative numbers, positive numbers, and zeros

Assumptions I'm making:

• The input array is valid and not null
• We can modify the original array in-place
• The relative ordering of non-zero elements must be preserved (this is a key constraint)

Data shape and hidden structure: The problem has a clear two-part structure:

1. Identify all non-zero elements and their relative order
2. Move all zeros to the end while preserving that order

The hidden structure is that we can think of this as a "partition" problem where we're partitioning elements by value (non-zero vs zero) while maintaining internal ordering.

This is a classic array manipulation problem that tests understanding of in-place operations, two-pointer techniques, and array traversal patterns.

2. Pattern Recognition

Identifying the most likely pattern or patterns

The most likely pattern here is "Two Pointers" or "Partitioning".

Why this problem fits that pattern

The problem asks us to move all zeros to the end of an array while maintaining the relative order of non-zero elements. This is a classic partitioning problem where we're essentially separating elements based on a condition (zero vs non-zero). The key signal is that we want to rearrange elements in-place while preserving some ordering property.

Core insight needed to solve it

The core insight is that we can use a two-pointer technique where one pointer tracks the position where the next non-zero element should be placed, and the second pointer scans through the array. This allows us to maintain the relative order of non-zero elements while effectively "moving" zeros to the end.

The pattern is particularly evident because:

1. We need to rearrange elements in-place (no extra array)
2. We want to preserve relative order of non-zero elements
3. We're essentially partitioning the array into two sections: non-zeros followed by zeros
4. The operation should be done in a single pass

This is fundamentally about maintaining an invariant where all elements before a certain pointer are non-zero, and we're building up that section while scanning forward.

3. Approach Evolution

My first instinct is to use a two-pointer technique because this problem asks us to rearrange elements in-place while maintaining relative order of non-zero elements. But let me think about the constraints more carefully.

If I use a brute-force approach where I iterate through the array and whenever I find a zero, I shift all subsequent elements left by one position, that would be O(n²) time complexity because for each zero found, I might need to shift up to n elements. This is inefficient and not optimal for large inputs.

Let me think about how to optimize this. I notice that if I maintain the invariant that all non-zero elements appear in their original relative order before all zeros, I can reduce it to O(n) time by making a single pass through the array.

I'm thinking of a two-pointer approach where one pointer tracks the position where I should place the next non-zero element, and the other pointer scans through the array. This way, I can ensure that all non-zero elements are moved to the front in their original order, and zeros naturally end up at the back.

The key insight here is that I don't need to preserve the exact positions of zeros - I just need to move all non-zero elements to the front while maintaining their relative order, and zeros will naturally fall into place at the end.

This approach works because:

1. I can make one pass through the array
2. I maintain a pointer that tells me where to place the next non-zero element
3. I can count how many zeros there are and fill the end of array with zeros
4. This gives me O(n) time and O(1) space complexity

The invariant I'm maintaining is: all elements from index 0 to i-1 are non-zero elements in their original relative order, and all elements from index i to n-1 are zeros.

Let me code this up carefully - I want to make sure I handle the edge cases properly and that my two pointers don't go out of bounds.

public void moveZeroes(int[] nums) {
    int writeIndex = 0;
    
    // First pass: move all non-zero elements to the front
    for (int readIndex = 0; readIndex < nums.length; readIndex++) {
        if (nums[readIndex] != 0) {
            nums[writeIndex++] = nums[readIndex];
        }
    }
    
    // Second pass: fill remaining positions with zeros
    while (writeIndex < nums.length) {
        nums[writeIndex++] = 0;
    }
}

4. Data Structure Choice

For this problem, I'll use a two-pointer approach with the input array itself as the primary data structure.

Primary Data Structure:

• Array (int[] nums) - This is the input array that we'll modify in-place to move all zeros to the end while maintaining relative order of non-zero elements.

Why this choice:

• The problem explicitly asks to "move all 0's to the end" which naturally maps to in-place array manipulation
• We need to preserve the relative order of non-zero elements, so we can't use sorting or other approaches that would disrupt ordering
• Using the input array directly satisfies the "in-place" requirement without additional space overhead

Time and Space Impact:

• Time Complexity: O(n) - we make one pass through the array
• Space Complexity: O(1) - only using a constant amount of extra space for the two pointers

Helper Structure:

• We don't need any additional data structures beyond the two integer pointers (left and right) that track our current position in the array
• The algorithm maintains a clean invariant throughout execution where all elements before the left pointer are non-zero in their original relative order

This approach is optimal because it uses only the existing input structure with minimal additional space, achieving the desired result in a single pass.

int left = 0; // Points to the position where we should place next non-zero element
int right = 0; // Scans through the array

5. Algorithm Walkthrough

Let me trace through the algorithm with the example array [0, 1, 0, 3, 12]:

Initial state: nums = [0, 1, 0, 3, 12], writeIndex = 0

Step 1: Process nums[0] = 0

• Since it's zero, we skip writing it to the write position
• writeIndex remains 0

Step 2: Process nums[1] = 1

• Since it's non-zero, we write it to position writeIndex = 0
• nums[0] = 1, so array becomes [1, 1, 0, 3, 12]
• Increment writeIndex to 1

Step 3: Process nums[2] = 0

• Since it's zero, we skip writing it to the write position
• writeIndex remains 1

Step 4: Process nums[3] = 3

• Since it's non-zero, we write it to position writeIndex = 1
• nums[1] = 3, so array becomes [1, 3, 0, 3, 12]
• Increment writeIndex to 2

Step 5: Process nums[4] = 12

• Since it's non-zero, we write it to position writeIndex = 2
• nums[2] = 12, so array becomes [1, 3, 12, 3, 12]
• Increment writeIndex to 3

Step 6: Post-processing - fill remaining positions with zeros

• Starting from writeIndex = 3, we set nums[3] = 0 and nums[4] = 0
• Final array: [1, 3, 12, 0, 0]

The algorithm correctly moves all non-zero elements to the front while maintaining their relative order, and fills the remaining positions with zeros. The key insight is that we can do this in two passes: first move non-zeros to the front, then fill the rest with zeros.

graph TD
    A[Start: [0,1,0,3,12]] --> B{nums[i] == 0?}
    B -- Yes --> C[Skip]
    B -- No --> D[Write to writeIndex]
    C --> E[writeIndex = 0]
    D --> E
    E --> F{All elements processed?}
    F -- No --> G[Process next element]
    F -- Yes --> H[Fill remaining with zeros]
    G --> B
    H --> I[End: [1,3,12,0,0]]

6. Java Solution

public class Solution {
    public void moveZeroes(int[] nums) {
        // Two-pointer approach: left pointer tracks the position where next non-zero should go
        int left = 0;
        
        // First pass: move all non-zero elements to the front
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != 0) {
                nums[left] = nums[right];
                left++;
            }
        }
        
        // Second pass: fill the remaining positions with zeros
        while (left < nums.length) {
            nums[left] = 0;
            left++;
        }
    }
}

This solution uses a two-pass approach with two pointers to efficiently move all zeros to the end while maintaining the relative order of non-zero elements. The first pointer (left) tracks where to place the next non-zero element, and the second pointer (right) scans through the array. After placing all non-zero elements at the beginning, we fill the remaining positions with zeros.

The approach ensures that:

1. Non-zero elements maintain their relative order
2. All zeros are moved to the end of the array
3. The operation is done in-place with minimal extra space
4. The solution handles all edge cases including empty arrays and arrays with no zeros

7. Complexity Analysis

Time Complexity: O(n)

The algorithm makes a single pass through the array with two pointers, where left and right traverse the array at most once each. Each element is visited a constant number of times, making the time complexity linear.

Space Complexity: O(1)

The solution uses only a constant amount of extra space for the two integer pointers (left and right) and temporary variables for swapping. No additional data structures like arrays, stacks, or hash maps are created, so the space complexity is constant.

Why these bounds are correct:

• The linear time complexity is optimal for this problem because we must examine each element at least once to determine the correct placement of zeros and non-zeros.
• The constant space complexity is achieved by performing in-place operations without requiring additional memory proportional to input size.
• The algorithm's performance scales linearly with input size, and the space usage remains constant regardless of array size.

Optimality:

This solution is optimal in both time and space complexity. Since we must inspect every element at least once to properly reorder them, O(n) time is unavoidable. The in-place swapping approach achieves the best possible space complexity of O(1) for this constraint.

The solution is near-optimal because it avoids any unnecessary passes or extra data structures that would increase either time or space complexity.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Handle gracefully with no operations needed
• Single element arrays: Array with just 0 or non-zero element
• Two elements: Both zero, one zero, or both non-zero

Duplicate Values and Repeated States

• Arrays with multiple consecutive zeros: Algorithm must handle grouping correctly
• Arrays where all elements are zero or all non-zero: Must not break the invariant

Boundary Conditions

• Zero at beginning of array: Should move to end without affecting other elements
• Zero at end of array: Should remain at end (no action needed)
• All zeros in array: Should return same array
• No zeros in array: Should return same array

Common Implementation Mistakes

1. Incorrect pointer management: Moving zero elements to the wrong positions or losing track of where zeros should go
2. Overwriting elements: Not preserving original values when swapping or shifting elements
3. Off-by-one errors: Processing one extra element or missing the last element during iteration
4. Not maintaining relative order: Changing the order of non-zero elements when they should remain in their original sequence
5. Failing to handle zero count correctly: Miscounting zeros during the two-pass approach or not properly tracking the insertion point

Implementation-specific Pitfalls

// Common mistake - incorrect loop bounds
for (int i = 0; i <= nums.length; i++) { // Wrong: should be < nums.length
    // ...
}

// Common mistake - not handling the case where all elements are zero
int writeIndex = 0;
for (int i = 0; i < nums.length; i++) {
    if (nums[i] != 0) {
        nums[writeIndex++] = nums[i];
    }
}
// Missing: fill remaining positions with zeros

The key is ensuring that we process all elements once and maintain the relative order of non-zero elements while efficiently placing zeros at the end.

9. Alternative Approaches

There are several alternative approaches to solving the move zeroes problem, each with different trade-offs:

Two-Pointer Approach (Alternative 1): Instead of using a separate array, we can use two pointers to partition the array in-place. We maintain one pointer for the position where the next non-zero element should go, and another to iterate through the array. When we encounter a non-zero element, we swap it with the element at the first pointer's position and advance the first pointer. This approach is more space-efficient but requires careful handling of the swap logic.

Stable Sort Approach (Alternative 2): We could treat this as a stable sorting problem where we sort elements by their "zero-ness" - placing all non-zero elements first, followed by zeros. This would involve a custom comparator that prioritizes non-zero elements. While this approach works, it's less efficient with O(n log n) time complexity and overkill for the simple partitioning requirement.

Count-Zeroes Approach (Alternative 3): We could first count the number of zeros, then overwrite the array from left to right with all non-zero elements, and finally fill the remaining positions with zeros. This requires two passes through the array but is conceptually simple.

The original solution using a separate array is preferred because it's clean, readable, and maintains the stable ordering of non-zero elements. The two-pointer approach is more space-efficient but introduces complexity in managing the in-place swaps and maintaining element order. The original approach's time complexity remains optimal at O(n) while being more straightforward to implement correctly.

The key trade-off is between space efficiency (two-pointer approach) and code clarity (original approach). The original solution's O(n) space usage is acceptable for most practical applications and makes the logic much more transparent to other engineers reading the code.

10. Test Cases

public class MoveZeroesTestCases {
    public static void main(String[] args) {
        // Test case 1: Basic example from problem
        int[] nums1 = {0, 1, 0, 3, 12};
        // Expected: [1, 3, 12, 0, 0]
        
        // Test case 2: All zeros
        int[] nums2 = {0, 0, 0};
        // Expected: [0, 0, 0]
        
        // Test case 3: No zeros
        int[] nums3 = {1, 2, 3};
        // Expected: [1, 2, 3]
        
        // Test case 4: Single element zero
        int[] nums4 = {0};
        // Expected: [0]
        
        // Test case 5: Single element non-zero
        int[] nums5 = {1};
        // Expected: [1]
        
        // Test case 6: Empty array
        int[] nums6 = {};
        // Expected: []
        
        // Test case 7: Zeros at beginning
        int[] nums7 = {0, 0, 1, 2};
        // Expected: [1, 2, 0, 0]
        
        // Test case 8: Zeros at end
        int[] nums8 = {1, 2, 0, 0};
        // Expected: [1, 2, 0, 0]
        
        // Test case 9: Multiple consecutive zeros
        int[] nums9 = {1, 0, 0, 0, 2};
        // Expected: [1, 2, 0, 0, 0]
        
        // Test case 10: Complex case with many zeros
        int[] nums10 = {0, 1, 2, 0, 3, 0, 4, 0};
        // Expected: [1, 2, 3, 4, 0, 0, 0, 0]
    }
}

The test cases cover:

• Basic functionality with mixed zeros and non-zeros
• Edge cases like empty arrays, single elements
• Boundary conditions with zeros at start/end
• Multiple consecutive zeros
• Complex scenarios with many zeros scattered throughout

Each test case should validate that all non-zero elements appear in their original relative order, followed by all zeros in their original relative order.

11. Final Summary

The core insight is to use a two-pointer technique to maintain the relative order of non-zero elements while efficiently moving zeros to the end. This approach works by maintaining a "write" pointer that tracks where the next non-zero element should be placed, ensuring all non-zero elements appear in their original relative order before any zeros. The solution is optimal with O(n) time and O(1) space complexity, making it ideal for large datasets where memory efficiency is crucial. The key strength lies in its single-pass execution and in-place modification that preserves the original sequence structure while achieving the required rearrangement.