use first row and first column as markers to track which rows/columns need to be zeroed. first check if first row and column themselves need clearing, then use them to mark other cells.
for cells [1..m-1][1..n-1], if cell is zero, mark matrix[r][0] = 0 and matrix[0][c] = 0. then in second pass, clear rows/columns based on these markers. finally clear first row/column if needed.
approach
- check if first row/column need clearing (store flags)
- use first row/column as markers for rest of matrix
- clear rows/columns based on markers
- clear first row/column if flags set
complexity
O(mn) time for three passes. O(1) space using matrix itself for markers.