We scan a matrix, find every cell that contains a zero, and set that cell's entire row and column to zero. The complication is that we cannot do it in a single pass that both reads and writes. If we see a zero at position (1,2) and immediately zero out row 1 and column 2, those newly written zeroes look identical to original zeroes when we read further cells, and they cascade across the matrix until everything is zero.

The core problem is how to record which rows and columns need to be zeroed without confusing original zeroes with the zeroes we write.

The follow-up moves us from O(mn) extra space down to O(m+n), then to O(1). Each step stores the same row/column information more compactly.

Key Constraints:

Intuition

Make a copy of the entire matrix, scan the copy for zeroes, and write zeroes into the original. Because the copy is never modified, every zero read from it is an original zero, so there is no confusion between original and newly written zeroes.

Algorithm

Example Walkthrough

Code

The bottleneck is space, not time. We copy the entire matrix only to remember where the zeroes were, but we do not need every cell's value. We need only which rows and which columns contain at least one zero, which is m + n flags instead of m * n integers. The next approach stores exactly that.

Intuition

Instead of copying the whole matrix, make one pass to record which rows and which columns contain a zero, then make a second pass to zero them out. Two sets, one for zero-rows and one for zero-columns, hold this information.

This separates the find phase from the write phase and uses O(m + n) space instead of O(m * n).

Algorithm

Example Walkthrough

Code

The two sets store at most m + n values, an improvement over copying the whole matrix. The follow-up asks for O(1) space, and the sets are external storage. The next approach stores the same row and column flags inside the matrix itself, in cells that can be read before they are overwritten.

Intuition

The first row has n cells, one per column, and the first column has m cells, one per row. Those m + n cells can hold the same row and column flags the two sets held, with no external storage. We use the first row to mark which columns should be zeroed and the first column to mark which rows should be zeroed.

Cell (0,0) belongs to both the first row and the first column, so it cannot serve as both a row flag and a column flag. We let matrix[0][0] track whether the first row should be zeroed and use a separate boolean variable firstCol to track whether the first column should be zeroed.

The order of operations matters. We mark first, then zero the inner cells, and handle the first row and first column last. Zeroing the first row or column earlier would overwrite the markers before the inner cells have read them.

Algorithm

Example Walkthrough

Code