Problem Statement

You are given an array of integers, and you need to move all zeroes to the end of the array. But, you are not allowed to change the order of the non-zero elements.

Approach 1

A simple way to solve this problem is to go through the array from left to right, and every time you encounter a zero, you search the rest of the array for a non-zero to swap with it. Time Complexity : O(N^2) & Space Complexity : O(1). It's an easy algorithm and needs no extra space but it's too slow. Here is a code sample for the algorithm in C#:
  1. class Program
  2. {
  3. static void Main(string[] args)
  4. {
  5. int[] array = new int[] { 3, 0, 0, 1, 2, 0, 4, 0 };
  6. int[] result = Approach1(array);
  7. //result is [ 3, 1, 2, 4, 0, 0, 0, 0 ]
  8. }
  9. static int[] Approach1(int[] array)
  10. {
  11. for (int i = 0; i < array.Length; i++)
  12. {
  13. //skip non-zero elements
  14. if (array[i] != 0)
  15. continue;
  16. //look for the nearest non-zero
  17. for (int j = i + 1; j < array.Length; j++)
  18. {
  19. if (array[j] == 0)
  20. continue;
  21. //swap it with our zero
  22. array[i] = array[j];
  23. array[j] = 0;
  24. break;
  25. }
  26. }
  27. return array;
  28. }
  29. }

Approach 2

Another way to solve this question is to create a new array, and place all non-zero elements into it. Then fill the remaining positions in the new array with zeroes. Time Complexity : O(N) & Space Complexity : O(N). It's a fast algorithm but it's not an ideal one because it needs extra space. Given below is a code sample illustrating this algorithm in C#,
  1. class Program
  2. {
  3. static void Main(string[] args)
  4. {
  5. int[] array = new int[] { 3, 0, 0, 1, 2, 0, 4, 0 };
  6. int[] result = Approach2(array);
  7. //result is [ 3, 1, 2, 4, 0, 0, 0, 0 ]
  8. }
  9. static int[] Approach2(int[] array)
  10. {
  11. int newArrayIndex = 0;
  12. int[] newArray = new int[array.Length];
  13. foreach (var element in array)
  14. {
  15. //skip all zeroes
  16. if (element == 0)
  17. continue;
  18. //add non-zero element to new array
  19. newArray[newArrayIndex] = element;
  20. newArrayIndex++;
  21. }
  22. //fill in the rest of the new array with zeroes
  23. for (int i = newArrayIndex; i < array.Length; i++)
  24. newArray[i] = 0;
  25. return newArray;
  26. }
  27. }

Approach 3

The ideal solution to this problem is to go through the array and move all non-zero elements to the left. This can be done by keeping the count of non-zero elements found so far. Time Complexity : O(N) & Space Complexity : O(1). This is an ideal solution to this interview question which takes minimum time and needs no extra space. This algorithm is implemented in the C# code below,
  1. class Program
  2. {
  3. static void Main(string[] args)
  4. {
  5. int[] array = new int[] { 3, 0, 0, 1, 2, 0, 4, 0 };
  6. int[] result = Approach3(array);
  7. //result is [ 3, 1, 2, 4, 0, 0, 0, 0 ]
  8. }
  9. static int[] Approach3(int[] array)
  10. {
  11. int nonZeroIndex = 0;
  12. //the number of non-zero elements we've seen so far
  13. for (int i = 0; i < array.Length; i++)
  14. {
  15. //skip all zeroes
  16. if (array[i] == 0)
  17. continue;
  18. //put this element to the index we're tracking
  19. array[nonZeroIndex] = array[i];
  20. nonZeroIndex++;
  21. }
  23. //fill the end of the array with zeroes.
  24. for (int i = nonZeroIndex; i < array.Length; i++)
  25. array[i] = 0;
  26. return array;
  27. }
  28. }