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, and return the matrix.

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?

Solutions:

For to solve it in `O(mn)`, use a copy of given matrix and go through every element of original matrix and update the copy matrix's row and column to zero if a zero if found in original matrix.

Space `O(m + n)` Solution:

```class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
ROWS, COLS = len(matrix), len(matrix[0])
rows = [0] * ROWS
cols = [0] * COLS
for r in range(ROWS):
for c in range(COLS):
if matrix[r][c] == 0:
rows[r] = 1
cols[c] = 1
for c in range(COLS):
for R in range(len(rows)):
if rows[R] == 1:
matrix[R][c] = 0
for r in range(ROWS):
for C in range(len(cols)):
if cols[C] == 1:
matrix[r][C] = 0
```

Space `O(1)` Solution:

```class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
ROWS, COLS = len(matrix), len(matrix[0])

rowZero = False

for r in range(ROWS):
for c in range(COLS):
if matrix[r][c] == 0:
matrix[0][c] = 0
if r > 0:
matrix[r][0] = 0
else:
rowZero = True
for r in range(1, ROWS):
for c in range(1, COLS):
if matrix[0][c] == 0 or matrix[r][0] == 0:
matrix[r][c] = 0
if matrix[0][0] == 0:
for r in range(ROWS):
matrix[r][0] = 0
if rowZero:
for c in range(COLS):
matrix[0][c] = 0

```

Ashwini Verma on Jan 31, 2022 at 04:01 am

×