Set Matrix Zeroes
MediumMarkers in the first row/col
First mark which rows and columns contain a 0, then go back and zero them out.
The idea
Use the first row and column as bookmarks: if a cell is 0, mark its row-head and col-head. Then zero out cells whose head is marked, handling the first row/col last.
1
1
1
1
0
1
1
1
1
zero at(1,1)
Step 1 of 3. Found a 0 at (1,1). Use row/column heads as bookmarks instead of extra arrays. zero at (1,1).
1/3
Optimal
timeO(rows·cols)spaceO(1)
No extra arrays.
1for r, c in every cell:2 if M[r][c] == 0: M[r][0] = M[0][c] = 03for r, c in every cell except row 0 and column 0:4 if M[r][0] == 0 or M[0][c] == 0: M[r][c] = 05if firstRowHadZero: zero every cell of row 06if firstColHadZero: zero every cell of column 0Input
- grid
- 3 × 3
Memory
- at
- row 1, column 1
- cells marked
- 1
- zero at
- (1,1)
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- matrix = [[1,1,1],[1,0,1],[1,1,1]]
- Output:
- [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
- Explanation:
- The 0's whole row and column go to 0.
Example 2
- Input:
- matrix = [[0,1],[1,1]]
- Output:
- [[0, 0], [0, 1]]
- Explanation:
- The corner 0 clears its row and column.
Example 3
- Input:
- matrix = [[1,2],[3,4]]
- Output:
- [[1, 2], [3, 4]]
- Explanation:
- No zeros → nothing changes.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.