Move Zeroes to End

Easy
0/40
profile
Contributed by
13 upvotes
Asked in companies
SAP LabsNewgen SoftwareDeloitte

Problem statement

Given an unsorted array of integers, you have to move the array elements in a way such that all the zeroes are transferred to the end, and all the non-zero elements are moved to the front. The non-zero elements must be ordered in their order of appearance.

For example, if the input array is: [0, 1, -2, 3, 4, 0, 5, -27, 9, 0], then the output array must be: [1, -2, 3, 4, 5, -27, 9, 0, 0, 0].

Expected Complexity: Try doing it in O(n) time complexity and O(1) space complexity. Here, ‘n’ is the size of the array.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of input contains a single integer ‘T’ representing the number of test cases.      

The first line of each test case contains a single integer ‘N’ representing the size of the array. The second line of each test case contains ‘N’ integers representing the elements of the array.

Output Format :

For each test case, modify the input array and print the output in a new line

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50 
1 <= N <= 10^6
-10000 <= A[i] <= 10000

Where ‘T’ is the number of test cases, ‘N’ is the size of the array, A[i] is the value of the element present at the ith index.

Time Limit:1sec

Sample Input 1:
1
7
2 0 4 1 3 0 28
Sample Output 1:
2 4 1 3 28 0 0
The explanation for Sample Output 1 :
All the zeros are moved towards the end of the array, and the non-zero elements are pushed towards the left, maintaining their order with respect to the original array.
Sample Input 2:
1
5
0 3 0 2 0
Sample Output 2:
3 2 0 0 0
Approaches (2)
Naive Approach

Hint: can you think of separating zero elements and non-zero elements in different containers?


 

Approach : 


 

We can create a new array of integers. As soon as we find a non-zero element, we can directly insert it into our new array. After that, we can insert all the left zero’s. 


 

We can easily calculate the number of left zeroes as : 

 

Size of original array = size of new array + number of zero’s (since we only took non-zero elements.



 

Algorithm : 


 

  • Initialise a non-zero pointer with 0 value.
  • Start traversing the array until we reach the end,
    • If a non-zero element is found, insert it in new array. Else,
    • If a zero element is found, just continue.
  • After we reach the end, total number of zero’s will be original array size - new array size.
  • Insert these many zeros into new array.



 

Time Complexity


 

Time complexity :


 

 O(N)


 

As we are only traversing the array only once.


 


 

Space Complexity

Space Complexity : 


 

O(N) 


 

Since we are creating a new array.

Code Solution
(100% EXP penalty)
Move Zeroes to End
Full screen
Console