Given an array of integers, move all the zeroes to the beginning of the array, leaving the order of the other integers unaltered. This operation has to be done in place.
Time Complexity O(n)
Java
package algos; public class moveZeroesToStart { public static int[] moveToStart(int[] input) { int n = input.length - 1, count = n-1; for (int i = n - 1; i >= 0; i--) { if (input[i] != 0) { input[count--] = input[i]; } } while (count >= 0) { input[count--] = 0; } return input; } public static int[] moveToEnd(int[] input) { int n = input.length, count = 0; for (int i = 0; i < n; i++) { if (input[i] != 0) { input[count++] = input[i]; } } while (count < n) { input[count++] = 0; } return input; } public static void main(String[] args) { int[] arr = { 3, 2, 0, 1, 5, 0, 0 }; arr = moveToStart(arr); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } System.out.println(); arr = moveToEnd(arr); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } }
Output
0 0 0 3 2 1 5 3 2 1 5 0 0 0
JavaScript
var moveToStart = function(input) { var n = input.length - 1; var count = n-1; for (var i = n - 1; i >= 0; i--) { if (input[i] !== 0) { input[count--] = input[i]; } } while (count >= 0) { input[count--] = 0; }; return input; }; var moveToEnd = function(input) { var n = input.length; var count = 0; for (var i = 0; i < n; i++) { if (input[i] !== 0) { input[count++] = input[i]; } } while (count < n) { input[count++] = 0; }; return input; }; var arr = [3, 2, 0, 1, 5, 0, 0]; arr = moveToStart(arr); for (var i = 0; i < arr.length; i++) { console.info(arr[i]); } console.log(); arr = moveToEnd(arr); for (var i = 0; i < arr.length; i++) { console.info(arr[i]); }
Follow Up
To do the opposite and move zeroes to the end of the array we need to start from the beginning with the counter at 0.