Set Matrix Zeroes

Given an m x n matrix of integers matrix, if an element is 0, set its entire row and column to 0's.

You must update the matrix in-place.

Follow up: Could you solve it using O(1) space?

Approach

Use the first row and first column as markers. First, record whether the first row or column should be zeroed. Then, for every zero cell, mark its row and column in the first row/column. Finally, zero out rows/columns based on these markers and handle the first row/column.

Why It Works

The marker cells indicate which rows and columns must be zeroed without extra space. A zero in any cell correctly propagates to its row and column, and the initial flags preserve the original state of the first row/column.

Complexity

• Time: O(m * n)
• Space: O(1)

Reference Implementation (Python)

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        rows, cols = len(matrix), len(matrix[0])
        first_row_zero = any(matrix[0][c] == 0 for c in range(cols))
        first_col_zero = any(matrix[r][0] == 0 for r in range(rows))

        for r in range(1, rows):
            for c in range(1, cols):
                if matrix[r][c] == 0:
                    matrix[r][0] = 0
                    matrix[0][c] = 0

        for r in range(1, rows):
            if matrix[r][0] == 0:
                for c in range(1, cols):
                    matrix[r][c] = 0

        for c in range(1, cols):
            if matrix[0][c] == 0:
                for r in range(1, rows):
                    matrix[r][c] = 0

        if first_row_zero:
            for c in range(cols):
                matrix[0][c] = 0
        if first_col_zero:
            for r in range(rows):
                matrix[r][0] = 0