Matrices

Matrices

Set Matrix Zeroes

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """

        list_of_zeros = []

        width = len(matrix)
        height = len(matrix[0])

        # find the 0s in the matrix
        for x in range(0, width):
            for y in range(0, height):
                if matrix[x][y] == 0:
                    # what should we do when we find a 0?
                    # naive approach, store loc in a list, and then once we've scanned the matrix, go back and set the rows/cols for that location to 0
                    list_of_zeros.append([x, y])

        for loc_of_zero in list_of_zeros:
            def set_row_col_zero(loc):
                x = loc[0]
                y = loc[1]

                # set row to zero
                for r in range(0, width):
                    matrix[r][y] = 0

                # set col to zero
                for c in range(0, height):
                    matrix[x][c] = 0

            set_row_col_zero(loc_of_zero)

• Key insight: Find the 0 in our matrix and store the location in a list. Once we've gone through our matrix, go back to our list and set its entire row and column to zero. I went with a naive, space inefficient approach for now, but will keep thinking about how to do this in O(m+n) and eventually constant space...