Move Zeros To Left
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

Question

Move Zeros To Left

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

Accepted Answer

I have used two pointer approach to solve it

Accepted Answer

Solution Using Extra space

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.

Space Complexity: O(n)Explanation:

O(N), where N is the number of array elements.

In the worst case, the number of elements in the vector used to store non-zero elements will be N. Hence the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where N is the number of array elements.

In the worst case, we are doing only two traversals of the array. Hence the overall time complexity will be O(N).

Accepted Answer

Two Pointers Based 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

Space Complexity: O(1)Explanation:

O(1).

In the worst case, constant extra space is required. Hence, the overall space complexity is O(1).

Time Complexity: O(n)Explanation:

O(N), where N is the number of elements in the array.

In the worst case, we are only traversing the array. Hence the overall time complexity will be O(N).