73. Set Matrix Zeroes
You receive an m × n integer matrix. Wherever a cell holds a 0, the rule fires: that cell's entire row and entire column must be set to 0.
The rule applies only to zeros that existed in the original matrix — zeros you write while applying it must not trigger it again. Update the matrix in place and return it.
The real interview question is memory. Cloning the matrix is trivial; recording which rows and columns contain a zero takes O(m + n) extra space and is a fine answer — but the sharpest solution marks everything using constant extra space.
Example 1:
Input: matrix = [[3, 5, 7], [4, 0, 6], [9, 8, 2]]
Output: [[3, 0, 7], [0, 0, 0], [9, 0, 2]]
Explanation: The only zero sits at row 1, column 1, so all of row 1 and all of column 1 become 0. Every other cell is untouched.
Example 2:
Input: matrix = [[0, 2, 3], [4, 5, 6], [7, 8, 0]]
Output: [[0, 0, 0], [0, 5, 0], [0, 0, 0]]
Explanation: Original zeros at (0, 0) and (2, 2) wipe rows 0 and 2 plus columns 0 and 2. Only the center cell survives — note that the freshly written zeros never fire the rule themselves.
Constraints:
- 1 ≤ m, n ≤ 200
- -2³¹ ≤ matrix[i][j] ≤ 2³¹ - 1
Hints:
You cannot zero cells while you scan — a zero you just wrote is indistinguishable from an original one. Separate the phases: first record which rows and which columns contain a zero, then do all the wiping in a second pass. Two boolean arrays (or hash sets) of sizes m and n are enough.
To reach O(1) extra space, let the matrix store its own bookkeeping: use row 0 and column 0 as the marker arrays — a zero anywhere in row i gets recorded as matrix[i][0] = 0, and in column j as matrix[0][j] = 0. Stash two booleans for whether row 0 / column 0 originally held a zero, zero out the inner cells from the markers, and wipe the first row/column last.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: matrix = [[3, 5, 7], [4, 0, 6], [9, 8, 2]]
Expected output: [[3, 0, 7], [0, 0, 0], [9, 0, 2]]