Here’s the problem statement:
Given an array of integers, manipulate its elements such that all zeros in it are placed after all the non-zero elements and the order of the non-zero elements is retained.
For example:
The array: [1, 45, 0, 7, 0, 5, 0, 0]
Output: [1, 45, 7, 5, 0, 0, 0, 0]
Let’s dive into the solution:
Here are two ways to solve this problem:
Approach 1:
Maintain a variable front to store the index of the last placed non-zero element in the final array. Set it to 0 initially.
Iterate through the array while skipping over all zeros and on encountering a non-zero element, move it to the front of the array at the index pointed by the front variable. Increment front. after the complete iteration, all non-zero elements in the original order are at indices [0->front]. However the elements between [front+1->array.length-1] could have non-zero elements (as they were never wiped off) therefore, iterate through indices [front+1->array.length-1] setting them all to 0.
Time complexity: Every index is visited once during the first iteration through the array. The indices between [front+1->array.length-1] are visited one more time while filling 0s. Therefore all elements are visited at max 1 or 2 times throughout the algorithm therefore the overall time complexity is: O(N)
Space complexity: O(1)
Here’s the code for this solution in Java:
public void zeroes(int[] array) {
int front = 0;
for(int i = 0;i<array.length;i++) {//loop1
if(array[i]!=0) {
array[front++] = array[i];//loop1
}
}
while(front<array.length) { //loop2
array[front++] = 0;
}
}
Note that in case the number of 0s in the array is much > the number of nonzeros in the array, then using this algorithm we’ll be writing 0s many times in places where there already are 0s. For example if the input array is [0 0 0 0 1 0 0 0] then indices [1->array.length] will be overwritten with 0s again in loop2. Therefore the number of array writes will totally be = the total number of elements in the array.
Also in case all elements in this array are nonzero for example if the input array is [1 2 3 4] then too all elements in the array will be overwritten in loop1 stmt2.
Approach 2:
Let’s see if we can do better than Approach 1 this time:
Maintain a variable front to store the index of the last placed non-zero element of the array. Set it to 0 initially.
Iterate through the array while skipping over all zeros and on encountering a non-zero element, move it to the front of the array at the index pointed by the front variable by swapping it with the element array[front]. [array[front] will be either = 0 in case front<i (because if it were non-zero then either it would have been replaced with 0 correctly earlier in the algorithm) or front=i which would happen in case all the elements from 0->front in the original array are nonzero. (we swap front and i and do not instead set array[i] = 0 directly because if front=i then setting array[i] = 0 will cause nonzero elements to be wiped off in the final array. See comments in the code for further explanation on this)]
Since this time we set the elements to 0 (while swapping) therefore at the end of the iteration all nonzero elements will be at the front followed by all 0s till the end.
Time complexity: Every index is visited once during the the algorithm therefore the overall time complexity is: O(N)
Space complexity: O(1)
It is important to note that in case the number of 0s in the array is much > the number of nonzeros in the array, then using this algorithm we’ll not be writing 0s many times in places where there already are 0s which is unlike Approach 1. Instead, we’ll only be writing 2 elements (during swap) as many times as the number of non-zero elements in the array. For example if the input array is [0 0 0 0 1 0 0 0] there will only be 2 array writes(i.e. 1 swap) when (front = 0 and i =4). This is the reason that this algorithm will perform better in such a case than Approach 1.
However in case all elements in this array are nonzero for example if the input array is [1 2 3 4] then like Approach 1 all elements in the array will be overwritten at stmt1 (cos then front = i for all i).
Here’s the code for this solution in Java:
public void zeroes(int[] array) {
int i, front;
i = front = 0;
while(i<array.length) {
if(array[i]!=0) { //skip if the curr. element is 0, if not: the place it in its correct place
/* reason we're swapping and not simply setting array[i] to 0 using:
// array[p++] = array[i];
// array[i++] = 0;//stmt2
is: in case we have all elements!=0 in the array, like [2,1], then if we were to set array[i] = 0 in the algo, then we'd end up with: [0, 0] as stmt2 will set every element to 0. On the contrary, by swapping we're technically just swapping each element with itself in this case of all elements !=zero*/
int t = array[front];
array[front] = array[i];
array[i] = t;
front++;
i++;
}
else {
i++;
}
}
}
Please do let me know if you find this article useful. Also, it’ll be great if you’d provide some feedback. To reach out, please leave a comment in the Contact section. Thanks! Happy Coding! 🙂
The Code Scribbbler 