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

1. Two Pointers: We'll use two pointers: nonZeroIndex and currentIndex. nonZeroIndex keeps track of where the next non-zero element should be placed. currentIndex iterates through the entire array.

2. Iteration: We iterate through the array using currentIndex.

3. Non-Zero Element: If we encounter a non-zero element (nums[currentIndex] != 0), we swap it with the element at nonZeroIndex. Then, we increment both nonZeroIndex and currentIndex.

4. Zero Element: If we encounter a zero element, we only increment currentIndex. This effectively leaves the zero in its current position but allows non-zero elements to be shifted to the beginning.

5. Fill Remaining with Zeros: After iterating through the entire array, all non-zero elements will be at the beginning. The remaining positions are filled with zeros by default.

Explanation

The algorithm efficiently moves non-zero elements to the front of the array without needing extra space. The swap operation ensures the relative order of non-zero elements is preserved. The use of two pointers allows for in-place modification of the array.

Code (C#)

public class Solution {
    public void MoveZeroes(int[] nums) {
        int nonZeroIndex = 0; // Index to place the next non-zero element

        for (int currentIndex = 0; currentIndex < nums.Length; currentIndex++) {
            if (nums[currentIndex] != 0) {
                // Swap if a non-zero element is found
                int temp = nums[nonZeroIndex];
                nums[nonZeroIndex] = nums[currentIndex];
                nums[currentIndex] = temp;
                nonZeroIndex++; // Move nonZeroIndex to the next available spot
            }
        }
    }
}

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 use only a constant amount of extra space for the pointers. The modification is done in-place.