Move Zeros To Left

Easy
0/40
Average time to solve is 10m
profile
Contributed by
40 upvotes
Asked in companies
AdobeTech MahindraDell Technologies

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?
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2 
5
1 2 0 0 1
3
1 0 0
Sample Output 1 :
0 0 1 2 1
0 0 1
Explanation for sample input 1 :
For the first test case, the given array is { 1, 2, 0, 0, 1 }, if we move all the zeros to the left the modified array becomes { 0, 0, 1, 2, 1} which is our final answer. 

For the second test case, the given array is { 1, 0, 0}, if we move all the zeros to the left the modified array becomes { 0, 0, 1} which is our final answer.
Sample Input 2 :
1
5
1 2 3 4 5
Sample Output 2 :
1 2 3 4 5
Hint

Try to think of an approach using a data structure to store all the non-zero elements.

Approaches (2)
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:

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

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).

Space Complexity

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).

Code Solution
(100% EXP penalty)
Move Zeros To Left
Full screen
Console