Move Zeroes To End

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
175 upvotes
Asked in companies
AmazonSAP LabsMicrosoft

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:
2
7
2 0 4 1 3 0 28
5
0 0 0 0 1
Sample Output 1:
2 4 1 3 28 0 0
1 0 0 0 0
The explanation for Sample Output 1 :
In the first testcase, 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.

In the second testcase, All zero are moved towards the end, hence the only non-zero element i.e 1 is in the starting of the array
Sample Input 2:
2
5
0 3 0 2 0
4
0 0 0 0
Sample Output 2:
3 2 0 0 0
0 0 0 0
Hint

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

Approaches (2)
Naive method

 

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

O(N)

 

Since we are maintaining two pointers, and as soon as a non-zero pointer reaches the end, we stop. So the maximum numbers we are visiting is ‘N’ therefore complexity is O(N)

Space Complexity

O(N) 

 

Since we are creating a new array.


 

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