Problem Statement

You are given an array of integers where some elements are zero. Your task is to move all the zeroes to the end of the array, maintaining the relative order of non-zero elements. The solution must be:

• In-place (no extra array),
• O(1) space complexity,
• O(n) time complexity.

Example

Input: [4, 2, 0, 4, 0, 3, 0, 5, 0, 1]
Output: [4, 2, 4, 3, 5, 1, 0, 0, 0, 0]

The order of non-zero numbers is preserved. All zeroes are shifted to the end.

Algorithm Intuition

We use two pointers:

• z: points to the first zero index.
• n: looks for a non-zero element after the zero index.

Step-by-step:

1. Traverse the array from left to right.
2. Find the first zero (this is our target to be replaced).
3. Then find the next non-zero element after this zero.
4. Swap the zero with the non-zero.
5. Continue this process until no more swaps can be made.

Solution

public class MoveZeroes {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length <= 1) return;

        int z = 0; // pointer to 0
        int n = 1; // pointer to non-zero

        while (z < nums.length && n < nums.length) {
            // Move z to the next zero
            while (z < nums.length && nums[z] != 0) {
                z++;
            }

            // Ensure n always starts from after z
            if (n <= z) {
                n = z + 1;
            }

            // Move n to the next non-zero after z
            while (n < nums.length && nums[n] == 0) {
                n++;
            }

            // If both in range and ready to swap
            if (z < nums.length && n < nums.length) {
                // Swap nums[z] and nums[n]
                int temp = nums[z];
                nums[z] = nums[n];
                nums[n] = temp;
            }
        }
    }
}

Cleaner Swap (Optional)

If you’re using Java 8+ and want to swap with a helper function:

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

Then inside the moveZeroes method:

swap(nums, z, n);

Explanation of Time and Space Complexity

• Time Complexity:
  Each element is visited at most once, so the time complexity is O(n).
• Space Complexity:
  No extra array or data structure is used. Just variables z, n, and optionally temp. So the space complexity is O(1).

Key Constraints

• You must perform this in-place (don’t create a new array).
• Maintain relative order of non-zero numbers.
• Only use constant space.