Solutions

# Use two bool arrays to mark rows and columns to be zeroed, or use the first row and column of the matrix as markers (O(1) space)
# math

# O(n*m) time, O(n+m) space
def setZeroes(matrix: list[list[int]]) -> None:
    ROWS, COLS = len(matrix), len(matrix[0])
    rows = [False for _ in range(ROWS)]
    cols = [False for _ in range(COLS)]

    for r in range(ROWS):
        for c in range(COLS):
            if matrix[r][c] == 0:
                rows[r] = True
                cols[c] = True

    for r in range(ROWS):
        for c in range(COLS):
            if rows[r] or cols[c]:
                matrix[r][c] = 0

# O(n*m) time, O(1) space
def setZeroes(matrix: list[list[int]]) -> None:
    row_zero = False
    ROWS, COLS = len(matrix), len(matrix[0])

    for r in range(ROWS):
        for c in range(COLS):
            if matrix[r][c] == 0:
                matrix[0][c] = 0        # mark column in the first row
                if r > 0:
                    matrix[r][0] = 0    # mark row in the first column
                else:
                    row_zero = True     # mark the first row to be zeroed

    # Apply markers to inner matrix
    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
    
    # Handle first column
    if matrix[0][0] == 0:
        for r in range(ROWS):
            matrix[r][0] = 0

    # Handle first row
    if row_zero:
        for c in range(COLS):
            matrix[0][c] = 0