Problem Statement
leetcode problem link
Brute Force - hashset [Accepted]
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
zero_cols = set()
zero_rows = set()
ROWS = len(matrix)
COLS = len(matrix[0])
for row in range(ROWS):
for col in range(COLS):
if matrix[row][col] == 0:
zero_rows.add(row)
zero_cols.add(col)
for row in zero_rows:
for col in range(COLS):
matrix[row][col] = 0
for col in zero_cols:
for row in range(ROWS):
matrix[row][col] = 0
Editorial
Approach 1: Additional Memory Approach
class Solution(object):
def setZeroes(self, matrix: List[List[int]]) -> None:
R = len(matrix)
C = len(matrix[0])
rows, cols = set(), set()
# Essentially, we mark the rows and columns that are to be made zero
for i in range(R):
for j in range(C):
if matrix[i][j] == 0:
rows.add(i)
cols.add(j)
# Iterate over the array once again and using the rows and cols sets, update the elements
for i in range(R):
for j in range(C):
if i in rows or j in cols:
matrix[i][j] = 0
Approach 2: O(1) Space, Efficient Solution
class Solution(object):
def setZeroes(self, matrix: List[List[int]]) -> None:
is_col = False
R = len(matrix)
C = len(matrix[0])
for i in range(R):
# Since first cell for both first row and first column is the same i.e. matrix[0][0]
# We can use an additional variable for either the first row/column.
# For this solution we are using an additional variable for the first column
# and using matrix[0][0] for the first row.
if matrix[i][0] == 0:
is_col = True
for j in range(1, C):
# If an element is zero, we set the first element of the corresponding row and column to 0
if matrix[i][j] == 0:
matrix[0][j] = 0
matrix[i][0] = 0
# Iterate over the array once again and using the first row and first column, update the elements.
for i in range(1, R):
for j in range(1, C):
if not matrix[i][0] or not matrix[0][j]:
matrix[i][j] = 0
# See if the first row needs to be set to zero as well
if matrix[0][0] == 0:
for j in range(C):
matrix[0][j] = 0
# See if the first column needs to be set to zero as well
if is_col:
for i in range(R):
matrix[i][0] = 0
