Leetcode: Set Matrix Zeroes

Set Matrix Zeroes | LeetCode OJ

For each 0 in the matrix the corresponding row and column needs to be set 0.

1. Iterate over the matrix and mark the row and column wherever a 0 is encountered.
2. Iterate over the matrix again and set the element whose row or column is marked

Remarks:

1. O(2*m*n) time complexity for traversing the matrix twice.
2. O(m+n) space complexity for using sets of size m and n
3. 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