The problem
For every 0 in an m × n matrix, set its whole row and whole column to 0. Change the matrix in place, using only a constant amount of extra memory.
Examples
01
- Input
matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
- Output
[[1, 0, 1], [0, 0, 0], [1, 0, 1]]
02
- 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
- 1 ≤ m, n ≤ 200
- −2³¹ ≤ matrix[i][j] ≤ 2³¹ − 1
The idea
Zeroing as you go spreads: the new zeros would wipe out rows and columns they have no right to. So first note which rows and columns to clear, then clear them. Two lists of flags would cost m + n memory.
Store the flags in the matrix itself: a 0 at [r][c] is noted by writing 0 into [r][0] and [0][c]. The first row and column are overwritten by those notes, so check first — with two plain booleans — whether they held a 0 of their own. Clear the inner cells by the notes, then the first row and column last.
- Time
- O(m · n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: rows, cols = len(matrix), len(matrix[0]) # Use the first row and column as the notes of which columns and rows to clear. # Their own cells are needed for that, so remember separately whether they had a 0. first_row = 0 in matrix[0] first_col = any(matrix[r][0] == 0 for r in range(rows)) for r in range(1, rows): for c in range(1, cols): if matrix[r][c] == 0: matrix[r][0] = matrix[0][c] = 0 for r in range(1, rows): for c in range(1, cols): if matrix[r][0] == 0 or matrix[0][c] == 0: matrix[r][c] = 0 if first_row: for c in range(cols): matrix[0][c] = 0 if first_col: for r in range(rows): matrix[r][0] = 0