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

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 make use of** O(m + n) space**

In **solution 2** we shall make 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 the first-row value is “0”, then we set the row variable to “0”. Then we check if the first column value is “0” then we set the column variable 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++

#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