Hard · Marker Row and Column
Understand → Visualise → Practice.
If a cell is zero, set every cell in its row and column to zero using the first row and column as constant-space markers.
Record which rows and columns must be zeroed in the matrix's own first row and column, after noting separately whether those two lines contained a zero originally.
Note whether the first row and first column contain any zero.
For every zero at (r, c) outside them, set matrix[r][0] = 0 and matrix[0][c] = 0.
Zero inner cells whose row or column marker is 0, then zero the first row and column if they were flagged.
O(rows × cols) time and O(1) extra space.
Zeroing cells while still scanning turns new zeros into false markers and wipes out the whole matrix.
Read the full guide first: Matrices and 2-D Arrays.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.