Blank out every row and column holding a zero

If any cell of a grid is 0, set that cell's whole row and whole column to 0. Report the resulting grid.

Worked example#

1 1 1        1 0 1
1 0 1   ->   0 0 0
1 1 1        1 0 1

The single zero blanks its row and its column, and nothing else.

The trap#

Doing it as you read is wrong. Blank a row the moment you meet a zero and the zeros you just wrote look exactly like original ones, so the next row you look at gets blanked too, and the whole grid collapses.

So this is really a question about separating what you found from what you change. Read everything first, then write.

The obvious fix, and the better one#

Keep a set of rows to blank and a set of columns, fill them on a first pass, then blank on a second. Correct, and it costs rows + columns of extra memory.

There is a way that uses none. Use the grid's own first row and first column as those two sets. If grid[r][c] is zero, mark grid[r][0] and grid[0][c]. The marks live in cells that are going to be blanked anyway.

One thing does not fit: grid[0][0] would have to be the marker for both row 0 and column 0. So record whether the first row and the first column contain a zero in two ordinary variables before you start, and handle them at the very end.

note whether row 0 has a zero, and whether column 0 has one
for every cell not in row 0 or column 0:
    if it is zero: mark grid[r][0] and grid[0][c]
for every cell not in row 0 or column 0:
    if grid[r][0] or grid[0][c] is zero: blank it
blank row 0 if it was noted, and column 0 if it was

Why the order at the end matters#

Blank the first row before using it as a marker list and every column looks marked. The two noted variables exist precisely so the first row and column can be left until last, after nothing else needs to read them.

That is the useful idea here: when data is doing double duty as bookkeeping, the order of operations is the correctness argument.

Constraints#

• 1 <= rows, columns <= 200