Shift All The Zeroes To The End Of An Array

Rithik Banerjee

6y23.4k4100Article

Array Interview Questionfreshersshifting elements

4 Comments

Join the conversation! Your thoughts help the community grow.

Anandhi R4y ago
Using System; namespace ShiftZerosToRightInArray { class Program { static void Main(string[] args) { Console.Write("Enter Array length"); int inputArrLen = Convert.ToInt32(Console.ReadLine()); int[] Arr = new int[inputArrLen]; // { 1, 4, 5, 0, 3, 7, 1, 0, 0, 11,0,12 }; Console.Write("Please enter array inputs:"); for(int i=0;i< inputArrLen;i++) { Arr[i] = Convert.ToInt32(Console.ReadLine()); } Console.WriteLine("Your Input array is :"); foreach(int row in Arr) { Console.WriteLine(row); } Console.WriteLine("We are processing your array to shift all zeros to the right.."); int ArrLen = Arr.Length; int[] result = new int[ArrLen]; int j = 0, k = ArrLen; for (int i = 0; i < ArrLen; i++) { if (Arr[i] == 0) { result[k - 1] = Arr[i]; k--; } else { result[j] = Arr[i]; j++; } } Console.WriteLine("Printing the Output"); foreach (int row in result) { Console.WriteLine("Final output is " + row); } Console.ReadKey(false); } } }
Yogesh Bondi5y ago
How come in approaches 2 and 3, the time complexity is O(N). We are looping the array again, right?
- harpreet singh5y ago
  In 2 and 3, we are not executing any inner loop for every element of array selected in the outer loop. For loop will only be executed for handful of indexes where 0 needs to be added and that is more of a constant and therefore, being ignored while calculating big O.
- Rithik Banerjee5y ago
  A single loop will signify big O of n(loop counter).

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;
}
}