In this tutorial, we will be discussing the approaches to move all zeros to end of array.
Example:
Input: {0, 1, -2, 3, 0, 0, 5, -40, 9, 0}
Ouput: {1, -2, 3, 5, -40, 9, 0, 0, 0, 0}
Ouput: {1, -2, 3, 5, -40, 9, 0, 0, 0, 0}
Constraints:
- All zeros should be moved to right end of array.
- The order of non - zero elements should be maintained.
- No extra space is allowed, it should be done in-place.
Approach 1:
We can use count variable to count the frequenct of 0s. When we reach the end of array it means the frequency of 0s is counted. At last, we will start a loop to fill the remaining position of array with zeros.
Explanation:
- Declare and initialize
count = 0variable.(It will keep the frequency of 0s). - Start a loop (i) from left to the right of array and start traversing it.
- If we encounter an element which is not equal to 0.
Put that element into the position of count i.e arr[count] = arr[i], and increment count by 1. - Step 2 gets repeated until we traverse the whole array.
- When loop ends we will get the frequency count of 0s.
- Now, start a loop to fill up the remaining position of the array with zeros. The loop will run until count < length of array and fill up arr[count] with zero and increment count by 1.
Approach 1 code is implemented below.
public class MoveZeros {
public static void main(String[] args) {
int[] arr = { 0, 1, -2, 3, 0, 0, 5, -40, 9, 0 };
int n = arr.length;
moveZeros(arr, n);
printArray(arr, n);
}
private static void printArray(int[] arr, int n) {
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
public static void moveZeros(int[] arr, int n) {
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] != 0) {
arr[count] = arr[i];
count++;
}
}
while (count < n) {
arr[count] = 0;
count++;
}
}
}
Output:
1 -2 3 5 -40 9 0 0 0 0
Time Complexity: O(n), because we are traversing the whole length of array once.
Space Complexity: O(1), because no extra space is used.
Approach 2:
This approach follows the idea of swapping of zero and non-zero element when non-zero element is encountered.
Explanation:
- Declare and initialize a variable, say j = 0.
- Start traversing the array from i = 0 till i < length of array.
- If a non-zero element is encountered, swapping of arr[i], arr[j] is done and j is incremented.
- continue to the next element.
Approach 2 code is implemented below.
public class MoveZeroes {
public static void main(String[] args) {
int[] arr = { 0, 1, -2, 3, 0, 0, 5, -40, 9, 0 };
int n = arr.length;
// calling moveZeroes method
moveZeroes(arr, n);
// printing the array after moving zeroes
printArray(arr, n);
}
private static void printArray(int[] arr, int n) {
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
public static void moveZeroes(int[] arr, int n) {
int j = 0;
for (int i = 0; i < n; i++) {
if (arr[i] != 0) {
// swapping of zero and non-zero elements
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
j++;
}
}
}
}
Output:
1 -2 3 5 -40 9 0 0 0 0
Time Complexity: O(n), because we are traversing the whole length of array once.
Space Complexity: O(1), because no extra space is used.
This question has been asked in: Amazon, Paytm, Microsoft, Facebook.
