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. You must 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.

The only thing to be careful about is that we need to check if the first row and first column have any 0’s in them. If they do, we need to set the entire first row and first column to 0 at the end.

We can iterate over rows and columns from indices 1 to m - 1 and 1 to n - 1 respectively, to avoid affecting the first row and first column. Then we can use the first row and first column to mark which rows and columns need to be set to 0.

Then we iterate over the matrix again and set the rows and columns to 0 based on the markers in the first row and first column. Finally, we check if the first row and first column need to be set to 0 based on our initial check.

And we’re done!

Solution in Python


class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        ROWS, COLS = len(matrix), len(matrix[0])
        first_row_has_zero = any(matrix[0][c] == 0 for c in range(COLS))
        first_col_has_zero = any(matrix[r][0] == 0 for r in range(ROWS))

        # Step 1: Use first row and first column as markers
        for r in range(1, ROWS):
            for c in range(1, COLS):
                if matrix[r][c] == 0:
                    matrix[0][c] = 0
                    matrix[r][0] = 0

        # Step 2: Zero out cells based on markers in first row/col
        for r in range(1, ROWS):
            for c in range(1, COLS):
                if matrix[0][c] == 0 or matrix[r][0] == 0:
                    matrix[r][c] = 0

        # Step 3: Zero out the first row and column if needed
        if first_row_has_zero:
            for c in range(COLS):
                matrix[0][c] = 0

        if first_col_has_zero:
            for r in range(ROWS):
                matrix[r][0] = 0

Complexity

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

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

And we are done.