Recent Posts

Move Zeroes Problem

Written by

Anshuman Raina

Given: An Array with 0s filled intermittently, as seen below

Input: [1,0,2,0,0,0,3,4,0,0]

Output: [1,2,3,4,0,0,0,0,0,0]

Explanation: The Output, as shown above, should be achieved by moving all the zeroes to the end of the array.

The question at hand sounds easy, right? We only need to collect all the zeroes and move them to the end of the array. We will again have two approaches, based on the space complexity of the problem. These approaches are :

1. Using Extra Space (Another Array)
2. Using the same array (No Extra space)
Besides the above, we will also, in brief, specify what other ways are there to solve the problem. So, without further ado, let’s see the first approach.

# Using Extra Space (Another Array)
Firstly, we write the pseudo-code for this:

  1. Initialize a new array of the same size as given array.
  2. Iterate over given array and
    a. If element is nonzero, add it to new array. Increment the index of new array by 1.
    b. If element is zero, skip.
  3. Iterate over new array, from index current to length of the array, setting the value of elements as 0.

The above step is required in C++ because it does not initialize an array with default 0 in each position.
Transforming the above to C++, gives us the below result.

Code:

void moveZeroesWithExtraSpace(int zeroesArray[], int size)
{
	if (size == 1 || size == 0)
	{
		cout << "Sorry";
		return;
	}
	int temp[size], j = 0;
	for (int index = 0; index < size; index++)
	{
		if (zeroesArray[index] != 0)
		{
			temp[j] = zeroesArray[index];
			j++;
		}
	}
	for (; j < size; j++)
	{
		temp[j] = 0;	// As C++ does not initialize arrays with 0, no need for this in java
	}
	for (int index = 0; index < size; index++)
	{
		cout << temp[index] << " ";
	}
}
int main()
{
	int zeroesArray[] = { 1, 0, 2, 0, 0, 0, 3, 4, 0, 0 };
	moveZeroesWithExtraSpace(zeroesArray, 10);
	return 0;
}

Time complexity: O(N) // while we iterate through a for loop
Space complexity: O(N) // which implies that as the size increases, so does the space as we need another array of the same size.

# Using the same array (No Extra space)

Again, we write the pseudo-code for this:

Here, we Initialize two indices, an index iterating length and an index for non-zero values. The index will be used to iterate length, while non zero Index will point to positions where non zero values will be filled.

  1. Traverse the given array ‘arr’ from left to right.
  2. While traversing, maintain count of non-zero elements in array.
  3. Let the index be ‘non zero’.
    a. For every non-zero element arr[i], put the element at ‘arr[count]’ and increment ‘non zero index’.
  4. After complete traversal, all non-zero elements have already been shifted to front end and ‘count’ is set as index of first 0.
  5. Now all we need to do is that run a loop which makes all elements zero from ‘count’ till end of the array.

Transforming the above to C++, gives us the below result.

void moveZeroesWithoutExtraSpace(int zeroesArray[], int size)
{
	if (size == 1 || size == 0)
	{
		cout << "Sorry";
		return;
	}
	int nonZeroIndex = 0;
	for (int index = 0; index < size; index++)
	{
		if (zeroesArray[index] != 0)
		{
			if (index != nonZeroIndex)
			{
				zeroesArray[nonZeroIndex] = zeroesArray[index];	// Copying if nonZeroIndex and ZeroIndex variables are not at the same pos
			}
			nonZeroIndex++;
		}
	}
	for (; nonZeroIndex < size; nonZeroIndex++)
	{
		zeroesArray[nonZeroIndex] = 0;	// As C++ does not initialize arrays with 0, no need for this in java
	}
	cout << "Array is" << endl;
	for (int index = 0; index < size; index++)
	{
		cout << zeroesArray[index] << " ";
	}
}
int main()
{
	int zeroesArray[] = { 1, 0, 2, 0, 0, 0, 3, 4, 0, 0 };
	moveZeroesWithoutExtraSpace(zeroesArray, 10);
	return 0;
}

Time complexity: O(N) // while we iterate through a for loop
Space complexity:O(1)

Output:

1,2,3,4,0,0,0,0,0,0

Other Approaches:

– Quick Sort and then reversal
– Count Zeroes firsthand and then replace

Move Zeroes Problem