Set Matrix Zeroes — Step-by-Step Visualization

Algorithm Pattern

O(1) Space In-place Modification

Key Idea

We use the first row and first column of the matrix itself as storage for our markers. This allows us to avoid O(m+n) extra space. We just need two extra variables to track if the first row and column themselves should be zeroed.

Step-by-Step Approach

1. Check if the first row and first column have any zeroes originally.
2. Use matrix[r][0] and matrix[0][c] to store markers for the rest of the matrix (rows 1..m-1, cols 1..n-1).
3. Iterate through the inner matrix. If matrix[r][c] is 0, mark its row header (matrix[r][0]) and col header (matrix[0][c]) as 0.
4. Iterate again through the inner matrix and zero out any cell whose markers are 0.
5. Finally, zero out the first row and column if they contained zeroes initially (using the flags from step 1).

Common Gotchas

• Process the markers only after scanning the inner matrix to avoid overwriting them too early.
• The order of operations is critical when using the first row/col as markers.