Description
For every original zero in a matrix, set its whole row and column to zero in place.
Solution
def set_zeroes(matrix):
rows,cols = len(matrix),len(matrix[0])
first_row = any(x == 0 for x in matrix[0])
first_col = any(row[0] == 0 for row in matrix)
for r in range(1,rows):
for c in range(1,cols):
if matrix[r][c] == 0:
matrix[r][0] = matrix[0][c] = 0
for r in range(1,rows):
for c in range(1,cols):
if matrix[r][0] == 0 or matrix[0][c] == 0:
matrix[r][c] = 0
if first_row:
for c in range(cols):
matrix[0][c] = 0
if first_col:
for r in range(rows):
matrix[r][0] = 0Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[[1,0],[3,4]]]- Output
[[0,0],[3,0]]
The zero clears its row and column.
Example 2
- Input
[[[1,2]]]- Output
[[1,2]]
With no original zeros, nothing changes.
Example 3
- Input
[[[0],[2]]]- Output
[[0],[0]]
The zero clears the only column.
Approach
Remember whether the first row and column need clearing; use their remaining cells as markers for the interior.
Time & space
O(R C) time; O(1) space. R and C are the row and column counts.