Coders Packet

Shifting All Zero's to the End of the Array Using Java

By Lokeswara Reddy Ajjuguttu

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 12

Output:
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.

Download project

Reviews Report

Submitted by Lokeswara Reddy Ajjuguttu (LokeswaraAjjuguttu)

Download packets of source code on Coders Packet