Set Matrix Zeroes - Leetcode
Tags: algorithms, tutorial, interview, leetcode
Published: 2023-06-05 22:59:00


## Problem Description

Link to Question: https://leetcode.com/problems/set-matrix-zeroes/description/

Given an `n x m` integer matrix `matrix`, if an element is `0`, set its entire row and column to `0`'s.

## Using a New Matrix

- Create a new matrix → new_matrix.
- Traverse the `matrix` , whenever a 0 is encountered, set the corresponding row and column in the `new_matrix` to be zero.

### Code

```cpp
#include <bits/stdc++.h>

void set_zero(vector<vector<int>>& matrix, int row, int col)
{
	int n=matrix.size();
	int m=matrix[0].size();

	for(int i=0; i<n; i++)
		matrix[i][col] = 0;
	for(int j=0; j<m; j++)
		matrix[row][j] = 0;
}
void setZeros(vector<vector<int>> &matrix)
{
	//Create a new matrix
	auto v = matrix;

	int n=matrix.size(); //# rows
	int m=matrix[0].size(); //# cols
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<m; j++)
		{
			if(matrix[i][j]==0)
			{
				set_zero(v, i, j);
			}
		}
	}
	matrix = v;

}
```

### Complexity Analysis

- Time: 
{% katex inline %} 
  O(m*n*(m+n))
{% endkatex %}, where m+n is the time required to turn corresponding row, and column to 0.
- Space: {% katex inline %} O(m*n) {% endkatex %} used by `new_matrix`

## Space Improved Solution

We can improve the space, if we just mark the corresponding row and column that needs to be turn into 0s while traversing the matrix. Let’s do that:

- Inititialise two flag arrays, `row_flag[#rows]` , and `col_flag[#cols]`
    - `row_flag[i]` and `col_flag[i]` can take either of two values, -1 or 0.
    - ‘-1’ means keep this row or col as it is.
    - ‘0’ means  turn this row or col into 0.
- Traverse the `matrix`. On encountering a 0, mark the corresponding flags.
- Now using our flag arrays, make the required cells of the matrix to be ‘0’.

### Code

```cpp
#include <bits/stdc++.h>

void setZeros(vector<vector<int>> &matrix)
{
	int n=matrix.size();
	int m=matrix[0].size();
	
	vector<int> row_flag(n, -1);
	vector<int> col_flag(m, -1);

	for(int i=0; i<n; i++)
	{
		for(int j=0; j<m; j++)
		{
			if(matrix[i][j]==0)
			{
				//mark the row and column
				row_flag[i]=0;
				col_flag[j]=0;
			}
		}
	}

	//Change the cells of matrix using
	//flag arrays
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<m; j++)
		{
			//Change to '0' if any of the row or col
			//was marked
			if(row_flag[i] == 0 || col_flag[j] == 0)
				matrix[i][j]=0;
		}
	}
}
```

### Complexity Analysis

- Time:  {% katex inline %} O(m*n) {% endkatex %}
- Space: {% katex inline %} O(m+n) {% endkatex %} used by flag arrays.

## Optimal Solution

We want to get rid of the space used by our flag arrays. How about using the 0th row and 0th column as flag arrays for marking purposes?

It turns out we can! We need to take care of one little caveat. Since the cell matrix[0][0] can represent **two states only (0 and non-zero)**, so, it can be either part of the ***col_flag*** or **row_flag**. Let’s say. We make it the part of **row_flag** to mark the 0th row. Then, we require one more variable to handle marking the 0th column. The image makes it more clear.


![Using Matrix as Flag Arrays](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/z5ym2bky6clud11e2shh.png)



Here’s the Approach then, 

- Traverse the `matrix`, and mark rows and columns which has to be turned 0.
- Traverse the `matrix` *[1,1] → [n,m]* i.e except first row and first column, and turn a cell 0 if either one of its row or column is marked.
- [IMPORTANT] We will modify the **0th row** before the **0th column**. The reason is, there’s a chance that matrix[0][0] is changed from a non-zero value to zero by the independent variable `is_col0` ! This will be falsely signify that first row also needs to be turned into zeros!

### Code

```cpp
void setZeros(vector<vector<int>> &matrix)
{
	int n = matrix.size();
    int m = matrix[0].size();
    bool is_col0 = false; // Marker for 0th colum
    
    //Mark the Rows and Columns
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
          if (matrix[i][j] == 0) {
            // Mark ith row
            matrix[i][0] = 0;

            // Mark jth column with care!
            if (j != 0) // any other column than 0th
              matrix[0][j] = 0;
            else
              is_col0 = true;
          }
        }
    }
	//Change the matrix from [1,1]=>[n-1,m-1]
	for(int i=1; i<n; i++)
	{
		for(int j=1; j<m; j++)
		{
			if(matrix[i][0] == 0 || matrix[0][j] == 0)
				matrix[i][j] = 0;
		}
	}
	
	//Change 0th row first,
	//matrix[0][0] is 0th row's flag
	if(matrix[0][0] == 0)
		for(int j=0; j<m; j++)
			matrix[0][j] = 0;
	
	//Change 0th column 
	if(is_col0)
		for(int i=0; i<n; i++)
			matrix[i][0]=0;
        
}
```

### Complexity Analysis

- Time:  {% katex inline %} O(m*n) {% endkatex %}
- Space: {% katex inline %} O(1) {% endkatex %} Finally 🥺!