Example 1
ready- Input
matrix = [ [ 1, 1, 1 ], [ 1, 0, 1 ], [ 1, 1, 1 ] ]- Expected
[ [ 1, 0, 1 ], [ 0, 0, 0 ], [ 1, 0, 1 ] ]- Why
- the center zero clears its middle row and middle column
Set Matrix Zeroes
35 min · setZeroes()mediumOpen in LeetCode #73 ↗
One zero in a spreadsheet can wipe out a whole cross of cells.
You're given an m x n integer matrix. For every cell that is 0 in the original
matrix, set its entire row and its entire column to 0. Return the finished matrix.
Only the original zero positions decide which rows and columns are cleared. A zero you write during the transformation doesn't create another wave of changes.
You may update the input matrix itself. Either way, return the matrix after all required rows and columns have been cleared.
Constraints
1 <= m, n <= 100matrixhas exactlymrows, and every row has exactlynvalues.-1_000 <= matrix[i][j] <= 1_000
Hints
Remember before you write
First scan the untouched matrix and record every row and column containing a zero. Only then should you change values.
The matrix can hold its own notes
Instead of external sets, use matrix[row][0] to mark a row and matrix[0][col] to
mark a column. Apply those markers only after the marking pass ends.
One cell has two jobs
matrix[0][0] belongs to both the first row and first column, so it can't remember
both states. Save two booleans for whether the original first row and first column
contained a zero.
Follow-up
Can you perform the transformation with O(1) extra working space?
Visible cases
Examples
Example 2
ready- Input
matrix = [ [ 0, 1, 2, 0 ], [ 3, 4, 5, 2 ], [ 1, 3, 1, 5 ] ]- Expected
[ [ 0, 0, 0, 0 ], [ 0, 4, 5, 0 ], [ 0, 3, 1, 0 ] ]- Why
- two zeros in the first row clear that row plus the first and last columns
Example 3
ready- Input
matrix = [ [ 1, 2 ], [ 3, 0 ] ]- Expected
[ [ 1, 0 ], [ 0, 0 ] ]- Why
- a corner zero clears its row and column without spreading again
Interview signal
Asked at
AmazonMicrosoftMeta
Remember zero rows and columns
Changing cells during the first scan is dangerous: a newly written zero could be mistaken for an original one. Scan once to collect the affected row and column indices, then make a second pass to apply them.
def set_zeroes(matrix: list[list[int]]) -> list[list[int]]:
zero_rows: set[int] = set()
zero_cols: set[int] = set()
for row in range(len(matrix)):
for col in range(len(matrix[0])):
if matrix[row][col] == 0:
zero_rows.add(row)
zero_cols.add(col)
for row in range(len(matrix)):
for col in range(len(matrix[0])):
if row in zero_rows or col in zero_cols:
matrix[row][col] = 0
return matrixTime O(m·n) for the two full scans. Space O(m+n) for the two sets.
First-row and first-column markers
The matrix already has room to store the same information. Use the first cell of each row as its row marker — a stored zero meaning that row must be cleared. Use the first cell of each column the same way.
The top-left cell belongs to both marker lines, so two booleans remember whether the original first row and first column need clearing.
def set_zeroes(matrix: list[list[int]]) -> list[list[int]]:
rows, cols = len(matrix), len(matrix[0])
first_row_zero = any(matrix[0][col] == 0 for col in range(cols))
first_col_zero = any(matrix[row][0] == 0 for row in range(rows))
for row in range(1, rows):
for col in range(1, cols):
if matrix[row][col] == 0:
matrix[row][0] = 0
matrix[0][col] = 0
for row in range(1, rows):
for col in range(1, cols):
if matrix[row][0] == 0 or matrix[0][col] == 0:
matrix[row][col] = 0
if first_row_zero:
for col in range(cols):
matrix[0][col] = 0
if first_col_zero:
for row in range(rows):
matrix[row][0] = 0
return matrixThe order matters: save the first-row and first-column state, write all markers, clear the interior, then clear those two marker lines last.
Time O(m·n) — a constant number of passes. Space O(1) beyond the returned matrix.
LeetCode's version mutates the matrix in place and returns void; ours returns the matrix so the judge can compare it.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[
[
1,
0,
1
],
[
0,
0,
0
],
[
1,
0,
1
]
]Run: visible + custom · Submit: full suite