A sensor board reports readings in an m x n grid. A reading of 0 means a sensor failed, and a failed sensor spoils every reading in its row and its column.
Write clear_zero_lines(grid) that, in place, sets to 0 every cell that shares a row or a column with a cell that was 0 in the original grid. It returns None.
Only zeros that were there at the start count: a cell that you set to 0 does not spread any further.
g = [[1, 1, 1],
[1, 0, 1],
[1, 1, 1]]
clear_zero_lines(g)
g # [[1, 0, 1],
# [0, 0, 0],
# [1, 0, 1]]
g = [[0, 1, 2, 0],
[3, 4, 5, 2],
[1, 3, 1, 5]]
clear_zero_lines(g)
g # [[0, 0, 0, 0],
# [0, 4, 5, 0],
# [0, 3, 1, 0]]
1 <= m, n <= 600; values are 32-bit signed integers.- Clearing the whole row and column again for every zero you meet can cost O(m·n·(m + n)), too slow when zeros are common. Aim for O(m·n) time. Remembering which rows and columns to clear in two extra lists is fine; the stretch goal is O(1) extra space.
Show hint
you need to know, for each row and each column, whether it held a zero. The grid's own first row and first column could store that information, as long as you remember separately what they held themselves.