Last Updated: 15 Jan, 2021

Move Zeros To Left

Easy

Asked in companies

Solve now

Problem statement

You are given an array 'ARR' of integers. Your task is to modify the array so that all the array elements having zero values get pushed to the left and all the array elements having non-zero value come after them while maintaining their relative order.

For example :

Consider the array { 1, 1, 0, 2, 0 }. 
For the given array the modified array should be {0,0,1,1,2} . 
Arrays { 0, 0, 1, 2, 1 } and  { 0, 0, 2, 1, 1 } are not the correctly reorganized array even if they have all the zero values pushed to the left as in both the arrays the relative order of non-zero elements is not maintained.

Follow Up :

Can you solve the problem in linear time, and constant space?

Input Format :

The first line of the input contains an integer 'T' representing the number of test cases or queries to be processed.
Then the 'T' test case follows.
The first line of each test case contains an integer 'N' denoting the number of elements in the array 'ARR'.
The second line of each test contains 'N' space-separated integers denoting the array elements.

Output Format :

For each test case, print the modified array in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^5
-10^9 <= ARR[i] <= 10^9

Where 'T' denotes the number of test cases, 'N' denotes the number of elements in the array ‘ARR’ respectively, and 'ARR[i]' denotes the ’i-th’ element of the array 'ARR'. 

Time limit: 1 second

Solve now

Approaches

01 Approach

The idea is to use an extra vector to store all the non-zero elements while maintaining their relative order. So we will first add all the non-zero elements to a vector and then iterate that vector backwards and start updating the array values from end. In the end we will set all the array values whose values were not updated to 0.

Steps:

Let storeNonZero be the vector that stores non-zero elements.
Do a for loop for i=0 to N-1
- If ARR[i] ! = 0 add ARR[i] to storeNonZero vector.
Set i=N-1
Iterate the storeNonZero vector from backwards. Let currElement denotes the current element.
- Set ARR[i] = currElement.
- Decrease i by 1.
while i>= 0
- Set ARR[i] = 0.
- Decrease i by 1.

Solve now

02 Approach

The idea is to use two pointers reader and writer to store the current reading index and the current writing index. We will initially place both the pointers at the end of the array. Then we will iterate the array backwards using reader pointer and for every non-zero element update the value of the element stored at writer pointer and decrement writer pointer by 1. In the end we will set all the array values whose values were not updated to 0.

Steps:

Initialize reader = N-1 and writer = N-1
While reader >= 0
- if ARR [reader] != 0
  - Set ARR [writer]= ARR [reader]
  - Decrease writer by 1.
- Decrease reader by 1.
Do a for loop for i = 0 to writer
- Set ARR[i] to 0

Solve now