LeetCode 73: Set Matrix Zeroes

link

We cannot update the matrix in one pass. Because, the original zeroes will conflict with the filled-in zeroes. We need at least two passes. Time cannot be better than $2 \cdot m \cdot n$ . We shall optimize for space.

O(m+n) space

In the first pass, for each encountered zero, we shall record its row and its column in two separate sets. In the second pass, we shall zero-out entire rows and entire columns based on the two sets.

Time: $\mathcal{O}(m \cdot n)$ , space: $\mathcal{O}(m + n)$ .

from itertools import product as cartesian

class Solution:
    def zero_out_row(self, r, mat, ncol) -> None:
        for c in range(ncol):
            mat[r][c] = 0

    def zero_out_col(self, c, mat, nrow) -> None:
        for r in range(nrow):
            mat[r][c] = 0

    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        zero_rows, zero_cols = set(), set()

        for r, c in cartesian( range(m), range(n) ):
            if matrix[r][c] != 0:
                continue
            zero_rows.add(r)
            zero_cols.add(c)

        for r in zero_rows:
            self.zero_out_row(r, matrix, n)
        
        for c in zero_cols:
            self.zero_out_col(c, matrix, m)

O(1) space

Say we have already determined if the first row and the first column should be zeroed out. Now, we can use the first row and the first column as the earlier two sets — to record zero-out decisions for the rest of the matrix. We do the two passes in LIFO manner — the last step in first pass becomes the first step in second pass.

First pass:
- We process first row and first column and save the two decisions in two variables.
- In the rest of the first pass, we process the rest of the matrix: matrix[1...(m-1)][1...(n-1)]. We use first row to record decisions about columns and first column to record decisions about rows.
Second pass:
- Zero-out matrix[1...(m-1)][1...(n-1)] based on the recorded decisions from first row and first column.
- Zero-out first (0-th) row and first (0-th) column based on the recorded decisions from the two variables.

Time: $\mathcal{O}(m \cdot n)$ , space: $\mathcal{O}(1)$ .

from itertools import product as cartesian

class Solution:
    def zero_out_row(self, r, mat, ncol) -> None:
        for c in range(ncol):
            mat[r][c] = 0

    def zero_out_col(self, c, mat, nrow) -> None:
        for r in range(nrow):
            mat[r][c] = 0

    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        zero_first_row = True if any( cell == 0 for cell in matrix[0]) else False
        zero_first_col = True if any( matrix[r][0] == 0 for r in range(m) ) else False

        for r, c in cartesian(range(1, m), range(1, n)):
            if matrix[r][c] != 0:
                continue
            # should zero-out row r
            matrix[r][0] = 0
            # should zero-out col c
            matrix[0][c] = 0
        
        for r in range(1, m):
            if matrix[r][0] != 0:
                continue
            self.zero_out_row(r, matrix, n)
        
        for c in range(1, n):
            if matrix[0][c] != 0:
                continue
            self.zero_out_col(c, matrix, m)

        if zero_first_row:
            self.zero_out_row(0, matrix, n)
        if zero_first_col:
            self.zero_out_col(0, matrix, m)

unreasonably effective