#73
Set Matrix Zeroes
Medium First row/column as markers
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
If a cell is 0, set its whole row and column to 0. Do it in place, ideally with O(1) extra space.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: any 0 wipes its whole row and column.
Why this works: mark rows and columns first, then wipe; wiping while scanning would create fake zeros. The first row and column can store the marks.
Example: [[1,1,1],[1,0,1],[1,1,1]]
zero at (1,1) → mark row 1, col 1→ [[1,0,1],[0,0,0],[1,0,1]]
✦Hints open one at a time
Using two boolean arrays (rows, cols) is the easy O(m + n) version.
For O(1), use the first row and first column as those arrays.
Remember separately whether the first row and first column themselves had a zero.
↗Approach
Record if row 0 / column 0 contain zeros. Mark matrix[r][0] and matrix[0][c] for every zero in the rest. Zero out inner cells using the marks, then handle row 0 and column 0 last.
</>Solution (Java)
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean row0 = false, col0 = false;
for (int c = 0; c < n; c++) if (matrix[0][c] == 0) row0 = true;
for (int r = 0; r < m; r++) if (matrix[r][0] == 0) col0 = true;
for (int r = 1; r < m; r++)
for (int c = 1; c < n; c++)
if (matrix[r][c] == 0) { matrix[r][0] = 0; matrix[0][c] = 0; } // mark
for (int r = 1; r < m; r++)
for (int c = 1; c < n; c++)
if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
if (row0) for (int c = 0; c < n; c++) matrix[0][c] = 0;
if (col0) for (int r = 0; r < m; r++) matrix[r][0] = 0;
}
}!Common mistake
Zeroing cells while still scanning — new zeros then wipe out rows and columns they shouldn't.
Complexity
- Time: O(m·n).
- Space: O(1).
Topic: 2D Arrays & Matrix
🎬 Episode 14: video coming soon