Set Matrix Zeroes
Spread every 0 in a matrix across its full row and column, in place.
Problem Understanding
Wherever an m x n integer matrix holds a 0, clear that cell's whole row and whole column to 0, modifying the matrix in-place rather than building a copy.
Strategy (O(1) Space)
We can use the first row and first column as markers.
- Check if first row/col originally have zeros. Store in flags.
- Iterate through the rest of the matrix. If
matrix[i][j] == 0, markmatrix[i][0]andmatrix[0][j]as 0. - Iterate again to set zeros based on markers.
- Handle first row/col separately using flags.
Use
matrix[i][0]to store row status.Use
matrix[0][j]to store col status.
Interactive Visualization
Watch how we use the first row and column as makers to avoid using O(MN) extra space.
Dry Run
Matrix: [[1,1,1],[1,0,1],[1,1,1]]
| Step | Action | State |
|---|---|---|
| 1 | Scan Row 0/Col 0 | No zeroes found. Flags=False. |
| 2 | Scan Inner | matrix[1][1] is 0. Mark [1][0]=0, [0][1]=0. |
| 3 | Apply Marks | [1][0] is 0 -> Set Row 1 to 0. [0][1] is 0 -> Set Col 1 to 0. |
| 4 | Apply Flags | Flags are False. Skip. |
Result: [[1,0,1],[0,0,0],[1,0,1]]
Edge Cases & Common Mistakes
Watch out for:
First Row/Col Overwrite: If you don't use separate flags (
firstRowZero), you might wipe out the markers needed for the rest of the matrix.Order of Operations: Process inner matrix first, THEN the first row/col based on flags.
Solution
O(M * N) Time, O(1) Space.
Set Matrix Zeroes Code
1var setZeroes = function(matrix) {2 const m = matrix.length, n = matrix[0].length;3 let firstRowZero = false, firstColZero = false;45 for(let i=0; i<m; i++) if(matrix[i][0] === 0) firstColZero = true;6 for(let j=0; j<n; j++) if(matrix[0][j] === 0) firstRowZero = true;78 for(let i=1; i<m; i++) {9 for(let j=1; j<n; j++) {10 if(matrix[i][j] === 0) {11 matrix[i][0] = 0;12 matrix[0][j] = 0;13 }14 }15 }1617 for(let i=1; i<m; i++) {18 for(let j=1; j<n; j++) {19 if(matrix[i][0] === 0 || matrix[0][j] === 0) {20 matrix[i][j] = 0;21 }22 }23 }2425 if(firstColZero) for(let i=0; i<m; i++) matrix[i][0] = 0;26 if(firstRowZero) for(let j=0; j<n; j++) matrix[0][j] = 0;27};