Move Zeroes easy

Problem Statement

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

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

Example 2:

Input: nums = [0] Output: [0]

Steps

The key idea is to use two pointers:

1. zeroIndex: Points to the first occurrence of a zero. It starts at 0.
2. currentIndex: Iterates through the array.

We iterate through the array using currentIndex. If we find a non-zero element at currentIndex, we swap it with the element at zeroIndex. Then, we increment both zeroIndex and currentIndex. If we find a zero, we only increment currentIndex. This effectively pushes all non-zero elements to the beginning of the array. At the end, any remaining positions in the array will be filled with zeroes.

Explanation

The algorithm maintains a partition in the array. The elements before zeroIndex are all non-zero elements in their original relative order. The elements after zeroIndex can be any combination of zeros and non-zeros. By swapping a non-zero element into the zeroIndex position, we extend the partition of non-zero elements. This process continues until we reach the end of the array, leaving all zeros at the end.

Code

class Solution {
    public void moveZeroes(int[] nums) {
        int zeroIndex = 0;  // Pointer to the next position for a non-zero element
        for (int currentIndex = 0; currentIndex < nums.length; currentIndex++) {
            if (nums[currentIndex] != 0) {
                // Swap non-zero element with element at zeroIndex
                int temp = nums[zeroIndex];
                nums[zeroIndex] = nums[currentIndex];
                nums[currentIndex] = temp;
                zeroIndex++; // Move zeroIndex to point to next position for a non-zero element
            }
        }
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
• Space Complexity: O(1). We perform the operation in-place without using any extra space proportional to the input size. The swap operation uses constant extra space.