Interview Questions On Array

Move all Zeros to the end of the array

Data structure questions with story like explanation.

In this article we will learn how to solve the most asked coding interview problem: “Move all Zeros to the end of the array” Problem Statement:

You are given an array of integers, your task is to move all the zeros in the array to the end of the array and move non-negative integers to the front by maintaining their order. Examples:

Example 1: Input: 1 ,0 ,2 ,3 ,0 ,4 ,0 ,1
Output:
1 ,2 ,3 ,4 ,1 ,0 ,0 ,0
Explanation:
All the zeros are moved to the end and non-negative integers are moved to front by maintaining order

Solutions:



Method 1:


Before we proceed with the solution, let's first gain a clear understanding of the logic.

  1. To move all zeros to the end of an array, we will create a temporary array called temp with the same size as the input array arr.

  2. We will start traversing the input array arr from the beginning.

  3. Whenever we encounter a non-zero element, we will copy it into the temp array temp at the next available position.

  4. After copying all the non-zero elements to the front of the temp array temp, we will fill the remaining positions of the temp array with zeros.

  5. Once we have moved all the non-zero elements to the front of the temp array temp and filled the remaining positions with zeros, we will have an array with all the zeros at the end.

  6. Finally, we can print out the modified array to verify that all zeros have been moved to the end.

  7. Time complexity: o(n)
    Space complexity: o(n)


Let's take a look at the program code: 


              import java.util.*;
          
              public class ZeroToEnd {
                  public static void zeroToEnd(int[] arr, int n) {
                      int[] temp = new int[n]; // Create a temp array of length input array
                      int k = 0; // for counting
              
                      // Traverse through array and if a non zero element is encountered then put this element in the temp array at zero index and increment index
                      for (int i = 0; i < n; i++) {
                          if (arr[i] != 0) {
                              temp[k] = arr[i];
                              k++;
                          }
                      }
              
                      // Fill the zeros in remaining places of temp array
                      while (k < n) {
                          temp[k] = 0;
                          k++;
                      }
              
                      for (int i = 0; i < n; i++) {
                          System.out.print(temp[i] + " ");
                      }
                  }
              
                  public static void main(String[] args) {
                      int[] arr = {1, 2, 0, 1, 0, 4, 0};
                      int n = arr.length;
                      zeroToEnd(arr, n);
                  }
              }

Method 2: Most efficient


Let's understand the logic:

  1. To move all zeros to the end of an array, we will create a temporary array called temp with the same size as the input array arr.

  2. First, we start traversing from the first occurrence index of zero in the input array. We do this by finding the index of the first zero element in the array and storing it in a variable called "k".

  3. We then take two variables "i" and "j". The variable "i" is initially set to the first occurrence index of zero and the variable "j" is set to the next index (i+1).

  4. We then check if the element at index "j" is non-zero. If it is non-zero, we swap the elements at indices "i" and "j", and increment both "i" and "j".

  5. If the element at index "j" is zero, we do not swap elements and simply increment "j".

  6. We repeat steps 3 and 4 until "j" reaches the end of the array.

  7. Finally, we print the modified array after all non-zero elements have been moved to the front and zeros to the end.


  8. Time complexity: o(n)
    Space complexity: o(1)


Let's take a look at the program code: 


              import java.util.*;
              public class Main {
                  public static void main(String[] args) {
                      int[] arr = {1, 2, 0, 1, 0, 4, 0};
                      zeroToEnd(arr);
                  }
                  public static void zeroToEnd(int[] arr) {
                      int k = 0;
                      // Finding the first occurrence of zero
                      for (int i = 0; i < arr.length; i++) {
                          if (arr[i] == 0) {
                              k = i;
                              break;
                          }
                      }
                      // Moving all non-zero elements to the front of the array
                      int j = k + 1;
                      for (int i = k; i < arr.length && j < arr.length;) {
                          if (arr[j] != 0) {
                              int temp = arr[j];
                              arr[j] = arr[i];
                              arr[i] = temp;
                              i++;
                          }
                          j++;
                      }
                      // Printing the modified array
                      for (int i : arr) {
                          System.out.print(i + " ");
                      }
                  }
              }

I hope this explanation helps! Let me know if you have any further questions.

Leave a comment