Shift All The Zeroes To The End Of An Array

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#:

class Program
{
    static void Main(string[] args)
    {
        int[] array = new int[] { 3, 0, 0, 1, 2, 0, 4, 0 };
        int[] result = Approach1(array);
        //result is [ 3, 1, 2, 4, 0, 0, 0, 0 ]
    }
    static int[] Approach1(int[] array)
    {
        for (int i = 0; i < array.Length; i++)
        {
            //skip non-zero elements
            if (array[i] != 0)
                continue;
            //look for the nearest non-zero
            for (int j = i + 1; j < array.Length; j++)
            {
                if (array[j] == 0)
                    continue;
                //swap it with our zero
                array[i] = array[j];
                array[j] = 0;
                break;
            }
        }
        return array;
    }
}

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#,

class Program
{
    static void Main(string[] args)
    {
        int[] array = new int[] { 3, 0, 0, 1, 2, 0, 4, 0 };
        int[] result = Approach2(array);
        //result is [ 3, 1, 2, 4, 0, 0, 0, 0 ]
    }
    static int[] Approach2(int[] array)
    {
        int newArrayIndex = 0;
        int[] newArray = new int[array.Length];
        foreach (var element in array)
        {
            //skip all zeroes
            if (element == 0)
                continue;
            //add non-zero element to new array
            newArray[newArrayIndex] = element;
            newArrayIndex++;
        }
        //fill in the rest of the new array with zeroes
        for (int i = newArrayIndex; i < array.Length; i++)
            newArray[i] = 0;
        return newArray;
    }
}

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,

class Program
{
    static void Main(string[] args)
    {
        int[] array = new int[] { 3, 0, 0, 1, 2, 0, 4, 0 };
        int[] result = Approach3(array);
        //result is [ 3, 1, 2, 4, 0, 0, 0, 0 ]
    }
    static int[] Approach3(int[] array)
    {
        int nonZeroIndex = 0;
        //the number of non-zero elements we've seen so far
        for (int i = 0; i < array.Length; i++)
        {
            //skip all zeroes
            if (array[i] == 0)
                continue;
            //put this element to the index we're tracking
            array[nonZeroIndex] = array[i];
            nonZeroIndex++;
        }

        //fill the end of the array with zeroes.
        for (int i = nonZeroIndex; i < array.Length; i++)
            array[i] = 0;
        return array;
    }
}