Move Zeroes

Array, Two Pointers

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]

Solutions

The problem is asking to move all zeros in the given array to the end while maintaining the relative order of the non-zero elements. This means that the sequence of non-zero numbers in the array should remain the same after all the zeros have been moved to the end.

Approach – Brute Force Technique

In the brute force approach, we use a simple bubble sort algorithm to push the zeros to the end of the array.

Steps

1. Get the length of the array: The variable n is assigned the length of the nums array.

2. Outer loop: The outer loop runs from i = 0 to i = n - 1. This loop iterates over each element in the array.

3. Inner loop: The inner loop runs from j = 0 to j = n - i - 2. This loop compares each element with its next element.

4. Check for zero: If the current element nums[j] is zero, then it needs to be moved to the end.

5. Swap elements: If nums[j] is zero, it is swapped with the next element nums[j + 1]. This is done by creating a temporary variable temp to hold the value of nums[j], then assigning nums[j] the value of nums[j + 1], and finally assigning nums[j + 1] the value of temp.

6. Repeat: The process is repeated for all elements in the array until all zeros have been moved to the end.

public class Solution
{

    public void MoveZeroes(int[] nums)
    {
        int n = nums.Length;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n - i - 1; j++)
            {
                if (nums[j] == 0)
                {
                    // Swap nums[j] and nums[j + 1]
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }
}

Complexity

• Time Complexity: O(n^2)

• Auxiliary Space: O(1)

Approach – Two Pointers Technique

In the optimized approach, we keep track of the last non-zero element found in the array. We then swap the current element with the last non-zero element if the current element is non-zero.

Steps

1. Initialize a pointer: The variable lastNonZeroFoundAt is initialized to 0. This pointer will keep track of the position where the next non-zero element should be moved.

2. Iterate through the array: The first for loop runs from i = 0 to i = nums.Length - 1. This loop iterates over each element in the array.

3. Check if the current element is non-zero: If the current element nums[i] is non-zero, then it needs to be moved to the position pointed by lastNonZeroFoundAt.

4. Move non-zero elements to the front: If nums[i] is non-zero, it is moved to the position nums[lastNonZeroFoundAt], and then the lastNonZeroFoundAt pointer is incremented. This effectively moves all non-zero elements to the front of the array, while maintaining their relative order.

5. Fill the rest of the array with zeros: The second for loop runs from i = lastNonZeroFoundAt to i = nums.Length - 1. This loop sets all the remaining elements in the array to zero.

public class Solution
{
 
    public void MoveZeroes(int[] nums)
    {
        int lastNonZeroFoundAt = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] != 0)
            {
                nums[lastNonZeroFoundAt++] = nums[i];
            }
        }
        for (int i = lastNonZeroFoundAt; i < nums.Length; i++)
        {
            nums[i] = 0;
        }
    }
}

Complexity

• Time Complexity: O(n)

• Auxiliary Space: O(1)