## Algorithm

Problem Name: 73. Set Matrix Zeroes

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

You must do it in place.

Example 1:

```Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
```

Example 2:

```Input: matrix = [[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]]
```

Constraints:

• `m == matrix.length`
• `n == matrix[0].length`
• `1 <= m, n <= 200`
• `-231 <= matrix[i][j] <= 231 - 1`

• A straightforward 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?

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>

void setZeroes_1(int **matrix, int m, int n) {
int *row_flag = (int *)calloc(m, sizeof(int));
int *col_flag = (int *)calloc(n, sizeof(int));

int i, j, ii, jj;
for (i = 0; i  <  m; i++) {
for (j = 0; j  <  n; j++) {
if (matrix[i][j] == 0) {
row_flag[i] = 1;
col_flag[j] = 1;
}
}
}
for (j = 0; j  <  n; j++) {
if (col_flag[j]) {
for (ii = 0; ii  <  m; ii++) {
matrix[ii][j] = 0;
}
}
}
for (i = 0; i  <  m; i++) {
if (row_flag[i]) {
for (jj = 0; jj  <  n; jj++) {
matrix[i][jj] = 0;
}
}
}
}
void setZeroes(int **matrix, int m, int n) {
int first_col_zero, first_row_zero;
first_col_zero = first_row_zero = 0;
int i, j;
/* scan first column */
for (i = 0; i  <  m; i++) {
if (matrix[i][0] == 0) {
first_col_zero = 1;
break;
}
}
/* scan first row */
for (j = 0; j  <  n; j++) {
if (matrix[0][j] == 0) {
first_row_zero = 1;
break;
}
}
/* scan the matrix */
for (i = 0; i  <  m; i++) {
for (j = 0; j  <  n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
/* set zeros except first column and first row */
for (i = 1; i  <  m; i++) {
for (j = 1; j  <  n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
/* set first column and first row to zero */
if (first_col_zero) {
for (i = 0; i  <  m; i++) matrix[i][0] = 0;
}
if (first_row_zero) {
for (j = 0; j  <  n; j++) matrix[0][j] = 0;
}
}

int main() {
int m, n, i, j;
m = 5;
n = 4;

int **matrix = (int **)calloc(m, sizeof(int *));
for (i = 0; i  <  m; i++)
matrix[i] = (int *)calloc(n, sizeof(int));

matrix[0][0] = 0; matrix[0][1] = 0; matrix[0][2] = 0; matrix[0][3] = 5;
matrix[1][0] = 4; matrix[1][1] = 3; matrix[1][2] = 1; matrix[1][3] = 4;
matrix[2][0] = 0; matrix[2][1] = 1; matrix[2][2] = 1; matrix[2][3] = 4;
matrix[3][0] = 1; matrix[3][1] = 2; matrix[3][2] = 1; matrix[3][3] = 3;
matrix[4][0] = 0; matrix[4][1] = 0; matrix[4][2] = 1; matrix[4][3] = 1;

setZeroes(matrix, m, n);

for (i = 0; i  <  m; i++) {
for (j = 0; j  <  n; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}

return 0;
}
``````
Copy The Code &

Input

cmd
matrix = [[1,1,1],[1,0,1],[1,1,1]]

Output

cmd
[[1,0,1],[0,0,0],[1,0,1]]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
// Top-down
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if(matrix.empty()) return;
int m = matrix.size(), n = matrix[0].size(), col0 = 1;
for(int i = 0; i < m; i++){
if(!matrix[i][0]) col0 = 0;
for(int j = 1; j  <  n; j++)
if(!matrix[i][j]) matrix[0][j] = matrix[i][0] = 0;
}

for(int i = 1; i  <  m; i++){
for(int j = 1; j  <  n; j++)
if(!matrix[i][0] || !matrix[0][j]) matrix[i][j] = 0;
if(!col0) matrix[i][0] = 0;
}
for(auto& x: matrix[0]) if(!matrix[0][0]) x = 0;
if(!col0) matrix[0][0] = 0;
}
};

// Bottom-up
class Solution {
public:
void setZeroes(vector < vector<int>>& matrix) {
if(matrix.empty()) return;
int m = matrix.size(), n = matrix[0].size(), col0 = 1;
for(int i = 0; i  <  m; i++){
if(!matrix[i][0]) col0 = 0;
for(int j = 1; j  <  n; j++)
if(!matrix[i][j]> matrix[0][j] = matrix[i][0] = 0;
}

for(int i = m - 1; i >= 0; i--){
for(int j = n - 1; j > 0; j--)
if(!matrix[i][0] || !matrix[0][j]) matrix[i][j] = 0;
if(!col0) matrix[i][0] = 0;
}
}
};
``````
Copy The Code &

Input

cmd
matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

Output

cmd
[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public void setZeroes(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
boolean firstRowZero = false;
boolean firstColZero = false;
for (int i = 0; i  <  rows; i++) {
if (matrix[i][0] == 0) {
firstColZero = true;
break;
}
}
for (int i = 0; i  <  cols; i++) {
if (matrix[0][i] == 0) {
firstRowZero = true;
break;
}
}
for (int i = 0; i  <  rows; i++) {
for (int j = 0; j  <  cols; j++) {
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
for (int i = 1; i  <  rows; i++) {
if (matrix[i][0] == 0) {
for (int j = 0; j  <  cols; j++) {
matrix[i][j] = 0;
}
}
}
for (int i = 1; i  <  cols; i++) {
if (matrix[0][i] == 0) {
for (int j = 0; j  <  rows; j++) {
matrix[j][i] = 0;
}
}
}
if (firstRowZero) {
for (int i = 0; i  <  cols; i++) {
matrix[0][i] = 0;
}
}
if (firstColZero) {
for (int i = 0; i  <  rows; i++) {
matrix[i][0] = 0;
}
}
}
}
``````
Copy The Code &

Input

cmd
matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

Output

cmd
[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const setZeroes = function(matrix) {
const rows = []
const cols = []
const rowNum = matrix.length
const colNum = matrix[0].length
for(let i = 0; i  <  rowNum; i++) {
for(let j = 0; j  <  colNum; j++) {
if(matrix[i][j] === 0) {
rows.push(i)
cols.push(j)
}
}
}
const mrows = rows.filter((el, idx, arr) => arr.indexOf(el) === idx)
const mcols = cols.filter((el, idx, arr) => arr.indexOf(el) === idx)
for(let i = 0; i < mrows.length; i++) {
matrix[mrows[i]] = new Array(colNum).fill(0)
}
for(let j = 0; j  <  mcols.length; j++) {
for(let k = 0; k  <  rowNum; k++> {
matrix[k][mcols[j]] = 0
}
}
return matrix
};
``````
Copy The Code &

Input

cmd
matrix = [[1,1,1],[1,0,1],[1,1,1]]

Output

cmd
[[1,0,1],[0,0,0],[1,0,1]]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def setZeroes(self, matrix):
m, n, x = len(matrix), len(matrix and matrix[0]), 0
for i in range(m):
for j in range(n):
if i < m - 1 and not matrix[i][j] and matrix[i + 1][j]: matrix[i + 1][j] = None
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if i > 0 and not matrix[i][j] and matrix[i - 1][j]: matrix[i - 1][j] = None
while x < m:
y = 0
while y < n:
if matrix[x][y] == 0: matrix[x], y = [0] * n, n
elif not matrix[x][y]: matrix[x][y] = 0
y += 1
x += 1
``````
Copy The Code &

Input

cmd
matrix = [[1,1,1],[1,0,1],[1,1,1]]

Output

cmd
[[1,0,1],[0,0,0],[1,0,1]]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _073_SetMatrixZeroes
{
public void SetZeroes(int[,] matrix)
{
var rowLength = matrix.GetLength(0);
var columnLenght = matrix.GetLength(1);

var rowZero = new bool[rowLength];
var columnZero = new bool[columnLenght];

int i, j;
for (i = 0; i  <  rowLength; i++)
for (j = 0; j  <  columnLenght; j++)
if (matrix[i, j] == 0)
{
rowZero[i] = true;
columnZero[j] = true;
}

for (i = 0; i  <  rowLength; i++)
for (j = 0; j  <  columnLenght; j++)
if (rowZero[i] || columnZero[j])
matrix[i, j] = 0;
}

public void SetZeroes_2(int[,] matrix)
{
var rowLength = matrix.GetLength(0);
var columnLenght = matrix.GetLength(1);

var firstRowHasZero = false;
var firstColumnHasZero = false;

int i, j;
for (i = 0; i  <  rowLength; i++)
if (matrix[i, 0] == 0) { firstColumnHasZero = true; break; }
for (i = 0; i  <  columnLenght; i++)
if (matrix[0, i] == 0) { firstRowHasZero = true; break; }

for (i = 1; i  <  rowLength; i++)
for (j = 1; j  <  columnLenght; j++)
if (matrix[i, j] == 0)
matrix[0, j] = matrix[i, 0] = 0;

for (i = 1; i  <  rowLength; i++)
for (j = 1; j  <  columnLenght; j++)
if (matrix[i, 0] == 0 || matrix[0, j] == 0)
matrix[i, j] = 0;
if (firstRowHasZero)
for (i = 0; i  <  columnLenght; i++)
matrix[0, i] = 0;
if (firstColumnHasZero)
for (i = 0; i  <  rowLength; i++)
matrix[i, 0] = 0;
}
}
}
``````
Copy The Code &

Input

cmd
matrix = [[1,1,1],[1,0,1],[1,1,1]]

Output

cmd
[[1,0,1],[0,0,0],[1,0,1]]