Set Matrix Zeroes LeetCode 73 Deep Dive

LeetCode 73 Set Matrix Zeroes gives you an m x n integer matrix. If any element matrix[i][j] is 0, you must set every element in row i and every element in column j to 0. The transformation must be done in-place — you cannot return a new matrix. The challenge is doing this correctly without letting an element you just zeroed trigger additional zeroing that was not part of the original problem.

The naive pitfall is zeroing as you find zeros. If you zero an entire row when you encounter matrix[2][3] == 0, you then encounter the newly-written zeros in that row, which would incorrectly trigger additional column zeroing. You must separate the detection phase from the zeroing phase: first identify all original zeros, then apply the zeroing.

The follow-up asks you to achieve O(1) extra space — meaning you cannot allocate a separate boolean array to remember which rows and columns need zeroing. The optimal solution turns the matrix against itself, using the first row and first column as the storage for those flags.

The first improvement over the naive in-place approach is to use two separate boolean arrays: zeroRows of size m and zeroCols of size n. In the first pass, scan every element. Whenever matrix[i][j] == 0, set zeroRows[i] = true and zeroCols[j] = true. These arrays record which rows and columns should be zeroed, derived only from the original matrix values.

In the second pass, iterate over every element again. If zeroRows[i] is true or zeroCols[j] is true, set matrix[i][j] = 0. Because the boolean arrays were populated entirely from the first pass, the second pass reflects only the original zeros — not zeros introduced during the second pass itself. The two-pass separation correctly handles the detection-before-zeroing requirement.

This approach is clean, easy to reason about, and runs in O(mn) time with O(m+n) space. It is the recommended solution for most interview settings unless the interviewer specifically asks for O(1) space. Once you have this working, the O(1) trick becomes easier to understand because it reuses the exact same two-pass logic — just with the matrix itself serving as the boolean arrays.

The O(1) approach uses matrix[i][0] (the first column) to record whether row i should be zeroed, and matrix[0][j] (the first row) to record whether column j should be zeroed. This works because those positions are just integer cells — you can overwrite them with 0 to signal that a row or column needs zeroing, mirroring what the external boolean arrays stored.

The collision at matrix[0][0] is the central subtlety. That cell sits at the intersection of row 0 and column 0. If you use it to mean "row 0 should be zeroed," it cannot simultaneously mean "column 0 should be zeroed." The standard resolution is to let matrix[0][0] represent the first row flag only, and introduce a single boolean variable firstColZero to represent whether the first column should be zeroed.

Aside from that one boolean, no additional O(m) or O(n) data structures are needed. The algorithm modifies the first row and first column as it scans, then uses those modified values in a second pass to apply zeros throughout the matrix. Finally, it handles the first row and first column themselves, using matrix[0][0] and firstColZero respectively.

The first pass scans every cell from row 1 to m-1 and column 1 to n-1 (skipping the first row and column for now, since those are being repurposed as flag storage). Whenever matrix[i][j] equals 0, write 0 into matrix[i][0] to mark row i and write 0 into matrix[0][j] to mark column j. These writes corrupt the original values of those cells — but that is acceptable because those cells are now flag storage, not original data.

Before or during this scan, you must also handle column 0 itself. Iterate down column 0 (or check it in the same pass): if any matrix[i][0] is already 0 in the original matrix, set firstColZero = true. Similarly, if matrix[0][0] is 0 in the original matrix, that means row 0 needs zeroing. The value matrix[0][0] naturally captures this since it is part of the first row scan.

After the first pass completes, matrix[i][0] encodes "should row i be zeroed?" for rows 1 through m-1, matrix[0][j] encodes "should column j be zeroed?" for columns 1 through n-1, matrix[0][0] encodes "should row 0 be zeroed?", and firstColZero encodes "should column 0 be zeroed?" These four pieces of state contain everything needed for the second pass.

The second pass applies the stored flags to the interior of the matrix — rows 1 through m-1 and columns 1 through n-1. For each cell matrix[i][j], check if matrix[i][0] == 0 (row i is flagged) or matrix[0][j] == 0 (column j is flagged). If either condition is true, set matrix[i][j] = 0. This correctly zeroes out every row and column indicated by an original zero, without the markers being corrupted mid-pass.

After the interior is zeroed, handle the first row separately. Check matrix[0][0]: if it equals 0, set every element in row 0 to 0. This uses the row-0 flag that was stored at matrix[0][0] during the first pass. Then handle the first column: check firstColZero. If it is true, set every element in column 0 to 0.

The ordering of these final steps is critical. You must zero the interior (rows 1..m-1, cols 1..n-1) before zeroing the first row and first column. If you zero the first row or column first, you overwrite the flag values that the interior pass still needs. Doing the interior last avoids this dependency. Within the final two steps, the order of first row vs. first column does not matter.

In Python: first set firstColZero = any(matrix[i][0] == 0 for i in range(m)). Then scan rows 1..m-1 and cols 1..n-1: if matrix[i][j] == 0, set matrix[i][0] = 0 and matrix[0][j] = 0. Interior second pass: for i in 1..m-1, for j in 1..n-1: if matrix[i][0] == 0 or matrix[0][j] == 0, set matrix[i][j] = 0. Then if matrix[0][0] == 0, zero row 0. Then if firstColZero, zero column 0. The full implementation is about 12 lines.

In Java: boolean firstColZero = false; scan column 0 in the first loop to set firstColZero. Then nested loops for the marking pass. The zeroing pass mirrors the Python logic. Use matrix[0][0] for the first-row flag and firstColZero for the first-column flag. Both Python and Java implementations run in O(mn) time and O(1) space. The algorithmic structure is identical across languages — only the syntax differs.

A common variation initializes firstColZero by checking if matrix[0][0] == 0 before the first pass, then handles the overlap differently. Both approaches are correct; the key invariant is that matrix[0][0] represents the first row and the boolean represents the first column, and the first row/column are zeroed last. Practicing both variants ensures you can reconstruct the solution under interview pressure.

Rotate Image (LeetCode 48) asks you to rotate an n x n matrix 90 degrees clockwise in-place. Like Set Matrix Zeroes, the trick is a two-step transformation: transpose the matrix (swap matrix[i][j] with matrix[j][i]), then reverse each row. No extra space is needed. The pattern of using the matrix itself as scratch space recurs across this problem family.

Valid Sudoku (LeetCode 36) validates a partially-filled 9x9 Sudoku board. It uses sets or encoded keys to detect duplicates across rows, columns, and 3x3 boxes. While not strictly an in-place transformation, it shares the matrix traversal pattern and the discipline of separating detection from action. Spiral Matrix (LeetCode 54) reads all elements in spiral order — another matrix traversal problem requiring careful boundary management.

The broader in-place matrix family includes problems like Game of Life (LeetCode 289), which uses the same two-pass trick as Set Matrix Zeroes: encode the new state in unused bits of the integer values to avoid needing a copy of the board. Recognizing that the matrix itself can serve as auxiliary storage is the unifying insight across all these problems. Mastering Set Matrix Zeroes builds the intuition for every problem in this family.