In this Java post, we will be learning how to move all non-zero elements to the starting of the Array and shift all zero's to the end of the Array by traversing the array only once.

**Problem Statement**:

Given an Array having both zeros and non-zero elements. We are required to move all the zeros to the end of the Array and all non-zeros elements to the beginning of the array. It is to be noted that we should not change the order of the non-zero elements in the Array.

**Approach 1(Taking extra Space):**

1. Take a auxiliary array of length equal to the length of the given array.

2. Take two pointers named *first* and *last* where *first *points to the beginning index of the array(*first*=0) and *last *points to the last index of the Array(*last*=array.length-1).

3. Now traverse the given array.

4. If we encounter a non-zero element, then we put that element at the index pointed by *first *pointer in the auxilary array. Then, increment the value of *first*(*first*++);

5. If we encounter a zero, then we put it at the index pointed by *last* in the auxilary array. Then decrease the *last* pointer(*last*--);

6. Continue this process till *first* is less than or equal to *last*.

int[] arr = {10, 5, 0, 3, 2, 0, 5, 0};

int[] auxilary_array = new int[arr.length];

int first = 0;

int last = arr.length - 1;

int i = 0;

while (first<=last) {

if (arr[i] != 0) {

auxilary_array[first++] = arr[i];

} else {

auxilary_array[last--] = arr[i];

}

i++;

}

**Complexity Analysis**:

Let, length of the array=n.

Then,

Time Complexity = O(n). As, we are iterating the Array only once.

Space Complexity = O(n). This is the space required for auxilary array.

**Approach 2(Without any Auxilary Space):**

1. This is a two pointers approach. Take two pointers named *traversal* and *last_non_zero_element*.

2. The *traversal* pointer is used to traverse the given Array.

3. And the pointer *last_non_zero_element* is used to point the last index of the non-zero element traversed till then.

4. Initially *traversal* pointer points to the first index of the array(*traversal*=0) and *last_non_zero_element* points to index=-1;

5. While traversing the given array, if we encounter a non-zero element then we increment the *last_non_zero_element* pointer and then swap the elements present at indices *last_non_zero_element* and *traversal*.

6. Continue this process untill we reach the end of the Array.

[Note: In Java we don't have the concept of pointers. Here both are not actual pointers like we refer them in C. They are taken just as integers to represent the indices of the Array].

*[Note: Similarly to shift all zero's to the starting of the array we should iterate the array from end. Here the pointer *last_non_zero_element* is decreased and then we swap the elements.].*

**Complexity Analysis:**

Let, length of the array=n.

Then,

Time Complexity = O(n). As, we are iterating the Array only once.

Space Complexity = O(1). As no extra space is being used here .

**Input:**

Enter the Length of the Array

10

Enter the Array

7 0 2 0 8 5 2 8 12Output:

Array after shifting the zeros to the end is:

7,2,8,5,2,8,12,0,0,0.

**Explanation:**

The Array elements are {7,0,2,0,8,5,2,0,8,12}

On applying the above procedure the array goes in these phases:

Here i is traversal pointer and j is last_non_zero_element.

{7,0,2,0,8,5,2,0,8,12}->i=0,j=-1

{7,0,2,0,8,5,2,0,8,12}->i=1,j=0

{7,0,2,0,8,5,2,0,8,12}->i=2;j=0

{7,2,0,0,8,5,2,0,8,12}->i=3;j=1

{7,2,0,0,8,5,2,0,8,12}->i=4;j=1

{7,2,8,0,0,5,2,0,8,12}->i=5;j=2

{7,2,8,5,0,0,2,0,8,12}->i=6;j=3

{7,2,8,5,2,0,0,0,8,12}->i=7;j=4

{7,2,8,5,2,0,0,0,8,12}->i=8;j=4

{7,2,8,5,2,8,0,0,0,12}->i=9;j=5

{7,2,8,5,2,8,12,0,0,0}->i=10;j=6

In this way the array is changed and final output is obtained.

Submitted by Lokeswara Reddy Ajjuguttu (LokeswaraAjjuguttu)

Download packets of source code on Coders Packet

## Comments