Move Zeros to End in Java

Moving zeros to the end in Java means re-arranging the elements of an array such that all the zeros are moved to the end of the array. In this problem statement, there is an integer array, write a Java function to move all zeros to the end of the array while maintaining the order of the non-zero elements.

Example: 1

Input:

[4, 0, 2, 0, 1, 0],

Output:

[4, 2, 1, 0, 0, 0].

Explanation: First we compare four and zero. four is a non-zero element so we don’t have to do anything. Later we compare 0 and 2 now we have to swap 2 with zero. Later we compare zero with zero we don’t have to do anything because both are zero. The next non-zero element is one so should replace one with zero. at the end we get three zeros and all the non-zero elements will be at starting positions.

Example: 2

Input:

[0, 1, 0, 3, 5]

Output:

[1, 3, 5, 0, 0]

Explanation: Herewe compare zero with one so the second is a non-zero element so we will be going to replace it with one. Then we check the next element it’s zero so we don’t have to do anything. Now we will check the next element it is three so we will replace it with zero and move on to the last element which is five. we have to replace five with the second last element Zero after doing the same will get zeros at the end.

Approach: Two-Pointer Technique

This approach involves using two pointers to iterate through the array simultaneously and perform operations on the array elements based on some condition. The two pointers can move in different directions, or they can move in the same direction at different speeds.

The Two-Pointer Technique is often used to solve problems that involve finding pairs of elements that meet certain conditions or performing some kind of sliding window operation on an array.

FileName: MoveZerosToEnd.java

public class MoveZerosToEnd {
 public static void main(String[] args) {
 int[] arr = {4, 0, 2, 0, 1, 0}; //this is an input array
 int i = 0; // here we initialize i pointer to the beginning of the array
 // iterate through the array using the j pointer
 for (int j = 0; j < arr.length; j++) {
 // if the current element at index j is non-zero, then we have to swap it with the element
at index i
 if (arr[j] != 0) {
 int temp = arr[j];
 arr[j] = arr[i];
 arr[i] = temp;
 // increment i to move it to the next non-zero element
 i++;
 }
 }
 //Fill the rest of the array with zeros from index I to the end of an array
 for (int j = i; j < arr.length; j++) {
 arr[j] = 0;
 }
 //this will go to print the output array
 for (int num: arr) {
 System.out.print(num + " ");
 }
 }
}

Output:

4 2 1 0 0 0

Complexity:

The time complexity of the algorithm to move all zeros to the end of an array using two pointers is O(n), where n is the length of the input array. This is because we only iterate through the array once using the second pointer, j, which takes O(n) time. We also perform a constant amount of work for each element in the array: swapping two elements, incrementing I, and filling zeros at the end. Since the number of elements is n, the total time complexity of the algorithm is O(n).

The space complexity of the algorithm of moving zeros to the end is O(1), as we are only using a constant amount of extra space for the two pointers and a temporary variable to perform the swap.

Approach: Count and Fill

In this approach, we count the number of zeros in the array and then fill the array with non-zero elements, followed by the remaining positions with zeros. Given sample code demonstrates this approach:

FileName: ZeroMove.java

import java.util.Arrays;
public class ZeroMove {
 // Moves all the zeros in the given integer array to the end of the array, while maintaining
 public static void moveZerosToEnd(int[] nums) {
 int countZeros = 0;
 for (int i = 0; i < nums.length; i++) {
 if (nums[i] == 0) {
 countZeros++; // count the number of zeros in the array
 } else {
 nums[i - countZeros] = nums[i]; // fill the array with non-zero elements
 }
 }
 for (int i = nums.length - countZeros; i < nums.length; i++) {
 nums[i] = 0; // fill the remaining positions with zeros
 }
 }
 //Test the moveZerosToEnd method with sample input array.
 public static void main(String[] args) {
 int[] nums = {0, 2, 0, 5, 11};
 moveZerosToEnd(nums);
 System.out.println(Arrays.toString(nums)); // [2, 5, 11, 0, 0]
 }
}

Output:

[2, 5, 11, 0, 0]

Complexity:

The time complexity of the given moveZerosToEnd method is O(n), where n is the length of the input array nums.

The space complexity of this code is O(1), as it only uses a fixed amount of additional space to store the count of zeros, and does not create any new data structures or arrays.

Swap Approach:

In this approach, we maintain two pointers, one pointing to the first zero we encounter and the other pointing to the next non-zero element. We swap the positions of the zero and the non-zero element and move the pointers until all the zeros are moved to the end of the array.

FileName: ZerosMoveToEnd.java

import java.util.Arrays;
class ZerosMoveToEnd {
 // Moves all the zeros in the given integer array to the end of the array, while maintaining
 // the relative order of the non-zero elements.
 public static void moveZerosToEnd(int[] nums) {
 int zeroIndex = 0; // initialize the index of the first zero element to 0
 for (int i = 0; i < nums.length; i++) { // loop through the entire array
 if (nums[i] != 0) { // if the current element is non-zero
 int temp = nums[i]; // swap the non-zero element with the element at the zero index
 nums[i] = nums[zeroIndex];
 nums[zeroIndex++] = temp;
 }
 }
 }
 // Test the moveZerosToEnd method with sample input array.
 public static void main(String[] args) {
 int[] nums = {0, 3, 0, 5, 10}; // initialize the input array
 moveZerosToEnd(nums); // call the moveZerosToEnd method to modify the array
 System.out.println(Arrays.toString(nums)); // print the modified array
 }
}

Output:

[3, 5, 10, 0, 0]

Complexity:

The for loop iterates over the input array nums once, which takes O(n) time. Within the loop, the if statement takes constant time. The time complexity of the swap operation in the loop is also constant because it only involves a temporary variable assignment and two array element accesses. so, the time complexity of the entire loop is O(n).

The space complexity of this code is O(1), as it only uses a constant amount of additional space to store the temporary variable temp, the index zeroIndex, and does not create any new data structures or arrays.

Approach: Single Pointer Approach

In this approach, we use a single pointer writeIndex to keep track of the position where the next non-zero element should be written in the array. The writeIndex pointer starts from 0 and iterates over the array elements.

FileName: MoveZerosToEnd.java

import java.util.Arrays;
public class MoveZerosToEnd {
 // Moves all the zeros in an integer array to the end, while maintaining the relative order of the non-zero elements.
 public static void moveZerosToEnd(int[] nums) {
 int writeIndex = 0;
 for (int num : nums) {
 if (num != 0) {
 nums[writeIndex++] = num;
 }
 }
 while (writeIndex < nums.length) {
 nums[writeIndex++] = 0;
 }
 }
 // Example usage of the moveZerosToEnd method.
 public static void main(String[] args) {
 int[] nums = {0, 2, 0, 7, 9};
 System.out.println("Original Array: " + Arrays.toString(nums));
 moveZerosToEnd(nums);
 System.out.println("Modified Array: " + Arrays.toString(nums));
 }
}

Output:

Original Array: [0, 2, 0, 7, 9]
Modified Array: [2, 7, 9, 0, 0]

Complexity:

The time complexity of this code is O(n), where n is the length of the input array nums. This is because we iterate through the array twice, once in the first loop to copy the non-zero elements to the front of the array, and again in the second loop to fill the remaining positions with zeros. However, each element in the array is only visited at most twice, and no nested loops or recursive calls are used, so the time complexity is linear with respect to the input size.

The space complexity of this code is O(1) because the algorithm uses a constant amount of extra memory regardless of the input size. Specifically, the writeIndex variable and the num variable in the enhanced for a loop both require constant space, and we do not create any new arrays or data structures during the execution of the algorithm. Therefore, the space complexity is constant with respect to the input size.