FAANGPrep Sprint
Set Matrix Zeroes
Spread every 0 in a matrix across its full row and column, in place.
MediumSolve on LeetCode
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
READY
0
1
2
3
0
0
1
2
0
1
3
0
5
2
2
1
3
1
5
Row 0 zero
No
Col 0 zero
No
Two flags remember whether column 0 and row 0 held a zero before they are reused as markers
Next
matrix[0][0] = 0: column 0 has a zero
Matrix
Watch how we use the first row and column as makers to avoid using O(MN) extra space.