POTD Solutions | 31 Oct’ 23 | Move all zeroes to end of array
Welcome to the daily solutions of our PROBLEM OF THE DAY (POTD). We will discuss the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up on your concepts of Two Pointers but will also help you build up problem-solving skills.
POTD 31 October: Move all zeroes to end of array
Given an array arr[] of n positive integers. Push all the zeros of the given array to the right end of the array while maintaining the order of non-zero elements. Do the mentioned change in the array in-place.
Example:
Input: arr[] = {1, 2, 0, 4, 3, 0, 5, 0};
Output: arr[] = {1, 2, 4, 3, 5, 0, 0, 0};Input: arr[] = {1, 2, 0, 0, 0, 3, 6};
Output: arr[] = {1, 2, 3, 6, 0, 0, 0};
Move all zeroes to end of the array Using Two Pointer Technique:
The idea is to use the two pointer approach, as we know for any non zero element its position can be its current position or at the previous index where 0 is present, so when we encounter a non zero element we will swap the values at both the index and increment both of them.
Step-by-step approach:
- Initialize a variable j equal to 0.
- Run a loop i from 0 to n.
- if the value at current index is non zero then swap the values at index i and j and increment j by 1.
below is the implementation of the approach.
C++
class Solution { public : // Function to push all the non-zero elements in the // array to the end, maintaining their original order. void pushZerosToEnd( int arr[], int n) { // Initialize a variable j to keep track of the // position to which non-zero elements should be // moved. int j = 0; // Loop through the array to find non-zero elements // and move them to the position indicated by 'j'. for ( int i = 0; i < n; i++) { if (arr[i] != 0) { // Swap the non-zero element at index 'i' // with the element at index 'j', // effectively moving the non-zero element // to the 'j' position. swap(arr[j], arr[i]); // Increment 'j' to indicate the next // position for the next non-zero element. j++; } } } }; |
Java
class Solution { // Function to push all the non-zero elements in the // array to the end, maintaining their original order. void pushZerosToEnd( int [] arr, int n) { // Initialize a variable j to keep track of the // position to which non-zero elements should be // moved. int j = 0 ; // Loop through the array to find non-zero elements // and move them to the position indicated by 'j'. for ( int i = 0 ; i < n; i++) { if (arr[i] != 0 ) { // Swap the non-zero element at index 'i' // with the element at index 'j', // effectively moving the non-zero element // to the 'j' position. int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; // Increment 'j' to indicate the next // position for the next non-zero element. j++; } } } } |
Python3
class Solution: def pushZerosToEnd( self , arr, n): # Initialize a variable j to keep track of the # position to which non-zero elements should be # moved. j = 0 # Loop through the list to find non-zero elements # and move them to the position indicated by 'j'. for i in range (n): if arr[i] ! = 0 : # Swap the non-zero element at index 'i' # with the element at index 'j', # effectively moving the non-zero element # to the 'j' position. arr[j], arr[i] = arr[i], arr[j] # Increment 'j' to indicate the next # position for the next non-zero element. j + = 1 |
Time Complexity: O(N), As we are running a nested loop of size N, So overall time complexity becomes O(N).
Auxiliary Space: O(1), As we are not using any extra space.
Move all zeroes to end of the array using Frequency counting of Zeroes:
Traverse the given array ‘arr’ from left to right. While traversing, maintain count of non-zero elements in array. Let the count be ‘count’. For every non-zero element arr[i], put the element at ‘arr[count]’ and increment ‘count’. After complete traversal, all non-zero elements have already been shifted to front end and ‘count’ is set as index of first 0. Now all we need to do is run a loop that makes all elements zero from ‘count’ till end of the array.
Below is the implementation of the above approach.
C++
class Solution { public : void pushZerosToEnd( int arr[], int n) { int count = 0; // Count of non-zero elements // Traverse the array. If the element encountered is // non-zero, then replace the element at index // 'count' with this element for ( int i = 0; i < n; i++) { if (arr[i] != 0) { arr[count++] = arr[i]; // here, count is incremented } } // Now all non-zero elements have been shifted to // the front, and 'count' is set as the index of the // first 0. Make all elements 0 from count to the // end. while (count < n) { arr[count++] = 0; } } }; |
Java
class Solution { void pushZerosToEnd( int [] arr, int n) { int count = 0 ; // Count of non-zero elements // Traverse the array. If element encountered is // non-zero, then replace the element at index 'count' // with this element for ( int i = 0 ; i < n; i++) if (arr[i] != 0 ) arr[count++] = arr[i]; // here count is // incremented // Now all non-zero elements have been shifted to // front and 'count' is set as index of first 0. // Make all elements 0 from count to end. while (count < n) arr[count++] = 0 ; } } |
Python3
class Solution: def pushZerosToEnd( self ,arr, n): count = 0 # Count of non-zero elements # Traverse the list. If the element encountered is non-zero, # then replace the element at index 'count' with this element for i in range (n): if arr[i] ! = 0 : arr[count] = arr[i] # here, count is not incremented yet count + = 1 # Now all non-zero elements have been shifted to the front, # and 'count' is set as the index of the first 0. # Make all elements 0 from count to the end. while count < n: arr[count] = 0 count + = 1 |
Time Complexity: O(n) where n is the size of elements of the input array.
Auxiliary Space: O(1)
Contact Us