You are given matrix, a grid of integers with m rows and n columns. For every cell that holds
0, set every value in its row and every value in its column to 0.
Only the zeros that are there at the start count: a zero you write must not clear any more rows
or columns. Change matrix in place; there is nothing to return.
Using O(m + n) extra memory is fine. Using only a constant amount is a stretch goal.
Example 1
- Input
- matrix = [[5, 2, 7], [3, 0, 8], [6, 4, 9]]
- Output
- [[5, 0, 7], [0, 0, 0], [6, 0, 9]]
Example 2
- Input
- matrix = [[0, 4, 2, 0], [3, 5, 1, 6], [7, 8, -1, 9]]
- Output
- [[0, 0, 0, 0], [0, 5, 1, 0], [0, 8, -1, 0]]
Constraints
- 1 ≤ m, n ≤ 200
- −2³¹ ≤
matrix[r][c]≤ 2³¹ − 1, so any value, negative ones included, can sit next to a zero.
Show the pattern
Math and matrices
It is bookkeeping by row and column index: record which rows and columns hold a zero before writing any, so the new zeros never spread further. The first row and column can even hold that record themselves.
Show the approach
Writing zeros while you scan goes wrong: a zero you have just written looks like an original one and would clear even more. So split the work into two passes.
First pass: find every original zero, and mark its row and its column (two lists of booleans, or two sets). Second pass: set every cell whose row or column is marked to 0.
For the stretch goal, use the first row and first column as the marks: a zero at (r, c) sets
matrix[r][0] and matrix[0][c] to 0. Note first, in two booleans, whether the first row and the
first column held a zero themselves. Then clear the inner cells by reading the marks, and clear
the first row and column last, according to the two booleans.
Time: O(m × n) · Space: O(m + n), or O(1) with the first row and column as marks