Understanding Move Zeroes in Java

Introduction & Problem Explanation

The Move Zeroes problem requires us to modify an array in-place such that all occurrences of the number 0 are shifted to the end of the array, while maintaining the relative ordering of all non-zero elements.

Crucially, we must do this without creating a copy of the array (in-place operation), and we want to minimize the number of operations to keep it as efficient as possible. This is a common utility task in databases and garbage collection systems where active items need to be compacted.

The Algorithmic Approach

1. Using an Extra Array (O(n) Space)

We can create a new array of the same size, iterate through the original array to copy all non-zero elements first, and then fill the remaining positions with zeroes. Finally, we copy the temp array back. This is simple but requires O(n) extra memory, which violates the in-place constraint.

2. Two-Pointer In-Place Optimization (O(n) Time, O(1) Space)

We maintain a pointer insertPos initialized to 0, which tracks where the next non-zero element should be written. We iterate through the array:

1. If the current element is non-zero, we assign it to nums[insertPos] and increment insertPos.
2. If the current element is zero, we do nothing and proceed.

After scanning the array, all non-zero elements have been written to the front. We then run a simple loop starting from the current value of insertPos to the end of the array, setting all those indices to 0. This is optimal as it visits every element exactly once with zero extra memory allocation.

Step-by-Step Execution Walkthrough

Let's trace the optimized two-pointer compaction on the input array nums = [0, 1, 0, 3, 12]:

1. Step 1 (Initialization): Set insertPos = 0. This pointer is ready to write the first non-zero element we find.
2. Step 2 (Index i = 0, Value = 0): The value is 0. We do nothing and move to the next index. insertPos remains 0.
3. Step 3 (Index i = 1, Value = 1): The value is 1 (non-zero).
   • We write it at nums[insertPos]: nums[0] = 1.
   • Increment insertPos to 1. The array is now: [1, 1, 0, 3, 12].
4. Step 4 (Index i = 2, Value = 0): The value is 0. We do nothing. insertPos remains 1.
5. Step 5 (Index i = 3, Value = 3): The value is 3 (non-zero).
   • We write it at nums[insertPos]: nums[1] = 3.
   • Increment insertPos to 2. The array is now: [1, 3, 0, 3, 12].
6. Step 6 (Index i = 4, Value = 12): The value is 12 (non-zero).
   • We write it at nums[insertPos]: nums[2] = 12.
   • Increment insertPos to 3. The array is now: [1, 3, 12, 3, 12].
7. Step 7 (Filling Zeroes): The main loop finishes. Now, we fill the remaining slots from insertPos = 3 to the end of the array (nums.length = 5) with zeroes:
   • Write nums[3] = 0. Increment insertPos to 4.
   • Write nums[4] = 0. Increment insertPos to 5.
8. Step 8 (Completion): The array is now fully processed: [1, 3, 12, 0, 0]. The relative order of 1, 3, 12 is preserved, and all zeroes are successfully moved to the end.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• if (num != 0) nums[insertPos++] = num;: This compacts all active non-zero elements sequentially at the front of the array.
• while (insertPos < nums.length) nums[insertPos++] = 0;: This fills all remaining trailing elements with zeroes, effectively wiping out the leftover duplicates of elements that were shifted forward.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

import java.util.Arrays;

public class MoveZeroes {

    // Brute Force - O(n) with extra space
    public void moveZeroesBrute(int[] nums) {
        int[] temp = new int[nums.length];
        int index = 0;
        for (int num : nums) {
            if (num != 0) {
                temp[index++] = num;
            }
        }
        System.arraycopy(temp, 0, nums, 0, nums.length);
    }

    // Optimized - O(n) in-place
    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;
        }
    }

    public static void main(String[] args) {
        MoveZeroes solver = new MoveZeroes();
        int[] nums = {0, 1, 0, 3, 12};

        System.out.println("--- Move Zeroes Demonstration ---");
        System.out.println("Input Array: " + Arrays.toString(nums));

        System.out.println("\nExecuting In-Place Shift...");
        int insertPos = 0;
        for (int num : nums) {
            if (num != 0) {
                System.out.printf("  Found non-zero %d. Writing to insertPos %d.\n", num, insertPos);
                insertPos++;
            }
        }
        System.out.printf("  Filling remaining spots from index %d to %d with 0.\n", insertPos, nums.length - 1);
        
        int[] testNums = {0, 1, 0, 3, 12};
        solver.moveZeroes(testNums);
        System.out.println("Result Array: " + Arrays.toString(testNums));
    }
}

Conclusion

Solving the Move Zeroes problem highlights how we can leverage key data structures and algorithmic paradigms (like two pointers, hash maps, or dynamic programming) to significantly optimize runtime and simplify code complexity.