Problem Statement in English

You’re given an m x n matrix. If an element is 0, you must set its entire row and column to 0. Do it in-place. There must be no chain reaction.

Approach

You just need to be a little creative with implementing the solution. It doesn’t need any fancy techniques.

We can solve this problem by iterating over the matrix and marking the rows and columns that are to be set to 0. We can do this by marking the columns as None and then updating the rows to be 0. Finally, we can update all the None’s (only columns we marked from the first iteration of the matrix will be None) to be 0.

Solution in Python


class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:

        # this function makes a particular column with index `col`, None
        def makeColNone(col: int):
            # update the column to be None
            for r in range(len(matrix)):
                if matrix[r][col] != 0:
                    matrix[r][col] = None

        # iterate over the matrix
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):

                # if a cell is $0$
                if matrix[i][j] == 0:
                    # make the column None
                    makeColNone(j)

                    # now update the row to be 0
                    for col in range(len(matrix[i])):
                        # if the cell is not None and not 0
                        if matrix[i][col] != None and matrix[i][col] != 0:
                            matrix[i][col] = 0
                        # if the cell is $0$,
                        # make that column None as well
                        elif matrix[i][col] == 0:
                            makeColNone(col)
                    # move on to the next row
                    break

        # now make all the None's 0
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if matrix[i][j] == None:
                    matrix[i][j] = 0

Complexity

  • Time: O(m×n)O(m \times n)
    Since we iterate over the matrix, which has m×nm \times n elements.

  • Space: O(1)O(1)
    Since we use no extra space

And we are done.