Given an m x n integer matrix, whenever a cell is 0, set its entire row and its entire column to 0. Do it in place. Only zeros present in the original matrix count, not zeros you write.
- 1 <= m, n <= 200
- -2^31 <= matrix[i][j] <= 2^31 - 1
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Copying the matrix costs O(m * n) space, and two marker arrays cost O(m + n). We can reuse the matrix: the first cell of each row says "clear this row" and the first cell of each column says "clear this column". Cell [0][0] cannot mark both row 0 and column 0, so we keep a separate flag for column 0. Then we fill zeros from the bottom-right so the markers are read before they are overwritten.
Algorithm
- Scan every cell. If
matrix[i][0] == 0, setcol0 = true. Forj >= 1, ifmatrix[i][j] == 0, setmatrix[i][0] = 0andmatrix[0][j] = 0. - Go through rows from bottom to top, and columns
jfrom right to left down to 1. - Set
matrix[i][j] = 0ifmatrix[i][0] == 0ormatrix[0][j] == 0. - After each row, if
col0is true, setmatrix[i][0] = 0.
O(m * n)Space: O(1)class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: m, n = len(matrix), len(matrix[0]) col0 = False # must column 0 be cleared? for i in range(m): if matrix[i][0] == 0: col0 = True for j in range(1, n): if matrix[i][j] == 0: matrix[i][0] = 0 # mark row i matrix[0][j] = 0 # mark column j # fill from the bottom-right so markers are read before being overwritten for i in range(m - 1, -1, -1): for j in range(n - 1, 0, -1): if matrix[i][0] == 0 or matrix[0][j] == 0: matrix[i][j] = 0 if col0: matrix[i][0] = 0