Last Updated: 24 Jul, 2021
Move Zeroes to End
Easy
Asked in companies
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.
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
Approaches
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.
Approach 2 (optimized method)
Hint: can you maintain two different pointers for zero and non-zero elements and swap them within the same array?
Approach :
We will use two pointers :
- zero element pointer → points to the first zero encountered.
- Non - zero element pointer → points to the first non-zero number encountered.
Our job is to only push zero’s towards the end, so all the non-zero numbers before any occurrence of zero’s will stay as it is. Hence our Non-zero pointer will point only when we encounter a non-zero element after zero element pointer.
When both of our pointers are set, we can swap the elements present at these places within the same array. Move the zero-pointers ahead. We will also move the non-zero pointer until we find a non zero element.
As soon as the non-zero pointer reaches the end, we will stop.
Edge cases :
- If initially, we couldn’t find our zero pointer, which means there are no elements that are zero in the array, then we will return as it is.
- If we found a zero pointer, but we could not find a non-zero pointer, then it means there are only zero’s in the array. In this case, also we will simply return.
Similar problems