Set Matrix Zeroes
- 2 min read
- LC-Medium
- Math-and-geometry
3 years ago
Solution
- Straightforward way is to use a rows and cols set which keeps track of rows and columns on which there's a zero. You then loop through again and set the respective row and column values to 0. This is a bad solution which takes
O(m + n)space andO(mn)time. - Use the actual first row and column of the matrix to keep track of which rows and columns to set to 0
- For the overlapping top-left corner, have a separate variable
| Time | Space | Explanation |
|---|---|---|
O(mn) | O(1) |
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
zero_row = False
nrows, ncols = len(matrix), len(matrix[0])
for r in range(nrows):
for c in range(ncols):
if matrix[r][c] == 0:
# Mark top row (i.e. columns to turn to 0)
matrix[0][c] = 0
# Mark left column (i.e. rows to turn to 0)
# We check here if r == 0 because of the overlapping square on the top left
# We are using the top left column to indicate if the first column should be turned to zeroes
# So we need another variable for the first row
if r == 0:
zero_row = True
else:
matrix[r][0] = 0
# Our for loops have to start from 1, since we don't want to overwrite our first row and columns just yet. That comes after.
for r in range(1, nrows):
for c in range(1, ncols):
if matrix[0][c] == 0 or matrix[r][0] == 0:
matrix[r][c] = 0
# Checking first column
if matrix[0][0] == 0:
for r in range(nrows):
matrix[r][0] = 0
# Checking first row
if zero_row:
for c in range(ncols):
matrix[0][c] = 0