Example 1:

Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]

Example 2:

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

Follow up:

• A straight forward solution using O(mn) space is probably a bad idea.
• A simple improvement uses O(m + n) space, but still not the best solution.
• Could you devise a constant space solution?
Ok, this is one of those problems, we think we can solve it easily but when we start writing the code, you will be lost in finding the correct logic.

We shall solve this problem by using 2 solutions. Be sure to understand both the solutions, as solution 2 is depended on solution 1.

In solution 1 we shall take use of O(m + n) space
In solution 2 we shall take use of constant space i.e O(1)

Solution 1:

In this solution we take 2 different arrays. One for row[m] and one for column[n].

Then we traverse the matrix, if we find a 0 in arr[i][j] then make the corresponding row[i] and column [j] to 0.

Then again traverse the matrix, such that if the value of either row[i] or column[j] is “0” then make arr[i][j] to “0”.

As we are taking extra elements to store row and column values, the space complexity is o(m+n).
Hope the above explanation makes sense.

Solution 2:

Solution 2 is similar to solution 1.

In Solution 2 we shall take 2 variables row, column.

In the first iteration, we check if first row value is “0”, then we set the row variable to “0”. Then we check if first column value is “0” then we set to “0”.

By doing the above step, you guessed it right, we can totally use the first row and first column.

Then we can follow the solution 1 to solve this solution 2.

Hence we are using constant space.

In both the solutions we are doing in place solution.

Solution in C++

/*
* File     : make_matrix_zero.cpp
* Copyright: @ prodevelopertutorial.com
*/
#include<iostream>
#include<vector>

using namespace std;

void set_zero_O_m_n(vector<vector<int>>& matrix)
{
	int row_len = matrix.size();
	int col_len = matrix[0].size();
	int itr = 0;
	int i = 0;
	int j = 0;


	int row[row_len];
	int col[col_len];

    /* set all values of row[] as 0 */
	for (itr = 0; itr < row_len; itr++)
	{
		row[itr] = 1;
	}


    /* set all values of col[] as 0 */
	for (itr = 0; itr < col_len; itr++)
	{
		col[itr] = 1;
	}

	/*If matrix[i][j] is zero, then set the corresponding row and column to zero*/
	for (i = 0; i < row_len; i++)
	{
		for (j = 0; j < col_len; j++)
		{
			if (matrix[i][j] == 0)
			{
				row[i] = 0;
				col[j] = 0;
			}
		}
	}


	/*if row[i] or column[i] is zero, then make matrix[i][j] to zero*/
    for (i = 0; i < row_len; i++)
    {
        for (j = 0; j < col_len; j++)
        {
            if ( row[i] == 0 || col[j] == 0 )
            {
                matrix[i][j] = 0;
            }
        }
    }

}

void set_zero_constant_space(vector<vector<int>>& matrix)
{
	int row_len = matrix.size();
	int col_len = matrix[0].size();

	// take 2 varible, set it to 1.
	int row = 1;
	int column = 1;

    //check if there is 0 in the first row, then update row variable
	for(int j = 0; j < col_len; j++)
		if(matrix[0][j]==0) row = 0;

    //check if there is 0 in the first column, then update column variable
	for(int i = 0; i < row_len; i++)
		if(matrix[i][0]==0) column = 0;

    /*Now we can use 1st row and 1st column, and we can apply solution 1*/

    //scan all the elements and update into the first row and column
	for(int i = 1; i<row_len;i++)
	{
		for(int j = 1; j<col_len;j++)
		{
			if(matrix[i][j] == 0)
			{
				matrix[0][j] = 0;
				matrix[i][0] = 0;
			}
		}
	}

    //Now set all the rows and columns to zero if the element is zero
	for(int i = 1; i < row_len;i++)
	{
		for(int j = 1; j < col_len;j++)
		{
			if(matrix[0][j] == 0 || matrix[i][0] == 0)
				matrix[i][j] = 0;
		}
	}
    
    //now set zero for the first row and column
	if(column == 0) for(int i = 0; i < row_len; i++) matrix[i][0] = 0;
	if(row == 0) for(int j = 0; j < col_len; j++) matrix[0][j] = 0;
}

int main()
{
	vector<vector<int> > input = { 	{1,1,1},
	{1,0,1},
	{1,1,1}
};
cout<< "The input matrix is "<<endl;

for (int i = 0; i < input.size(); i++)
{
	for (int j = 0; j < input[0].size(); j++)
	{
		cout<< input[i][j]<<" ";
	}
	cout<<endl;
}


//set_zero_O_m_n(input);

set_zero_constant_space(input);


cout<< "The input matrix after modifing to zero is "<<endl;

for (int i = 0; i < input.size(); i++)
{
	for (int j = 0; j < input[0].size(); j++)
	{
		cout<< input[i][j]<<" ";
	}
	cout<<endl;
}



}

Output:

The input matrix is
1 1 1
1 0 1
1 1 1
The input matrix after modifing to zero is
1 0 1
0 0 0
1 0 1