Leetcode: Set Matrix Zeroes
1 min readDec 26, 2016
For each 0 in the matrix the corresponding row and column needs to be set 0.
- Iterate over the matrix and mark the row and column wherever a 0 is encountered.
- Iterate over the matrix again and set the element whose row or column is marked
Remarks:
- O(2*m*n) time complexity for traversing the matrix twice.
- O(m+n) space complexity for using sets of size m and n
- By using sets we can avoid checking for duplicate row and column insertions and also get constant lookup time. Using lists for the same thing will blow up the time complexity
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
row = set()
col = set()
for i in range(0, len(matrix)):
for j in range(0, len(matrix[0])):
if matrix[i][j] == 0:
row.add(i)
col.add(j) for i in range(0, len(matrix)):
for j in range(0, len(matrix[0])):
if i in row or j in col:
matrix[i][j] = 0