Move Zeroes - Java Solution

1. Introduction

In this post, we will explore a solution to the "Move Zeroes" problem, a common task in array manipulation. The objective is to shift all zeros in an integer array to the end while maintaining the relative order of the non-zero elements. Importantly, this must be done in-place, without creating a copy of the array.

Problem

Given an integer array nums, the challenge is to move all 0's to the end of the array while preserving the order of non-zero elements. The operation must be performed in-place.

Examples:

- Input: nums = [0,1,0,3,12]

Output: [1,3,12,0,0]

- Input: nums = [0]

Output: [0]

2. Solution Steps

1. Initialize a pointer insertPos to track the position where the next non-zero element should be placed.

2. Iterate through the array:

a. When a non-zero element is encountered, place it at the insertPos index and increment insertPos.

3. After all non-zero elements are moved to the front, fill the remaining array with 0's starting from insertPos.

4. The in-place swap ensures that the relative order of non-zero elements is maintained.

3. Code Program

public class MoveZeroes {
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 3, 12};
        moveZeroes(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    // Function to move zeroes to the end of the array
    public static void moveZeroes(int[] nums) {
        int insertPos = 0;
        for (int num : nums) {
            if (num != 0) {
                nums[insertPos++] = num;
            }
        }

        while (insertPos < nums.length) {
            nums[insertPos++] = 0;
        }
    }
}

Output:

1 3 12 0 0

Explanation:

1. moveZeroes: This function rearranges the array to move all zeroes to the end.

2. The insertPos variable keeps track of where the next non-zero element should be placed.

3. As the function iterates through the array, each non-zero element is moved to the position indicated by insertPos, and insertPos is incremented.

4. After all non-zero elements are moved to the front, the remaining part of the array is filled with zeroes.

5. This approach maintains the order of non-zero elements and performs the operation in-place, adhering to the problem's constraints.

6. The method efficiently solves the problem with a single pass through the array, resulting in O(n) time complexity and O(1) space complexity.