[LeetCode/Python] 73. Set Matrix Zeroes

📌 Problem

[LeetCode] 73. Set Matrix Zeroes

📌 Solution

Solution 1: Upgraded Version

Idea

• If we are allowed extra space, we can record:
  • all rows that must become zero
  • all columns that must become zero
• First pass: scan the matrix and store indices in two sets: zero_rows, zero_cols
• Second pass: set matrix[i][j] = 0 if i in zero_rows or j in zero_cols

Code

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        zero_rows, zero_cols = set(), set()

        # 1) record which rows/cols must be zero
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    zero_rows.add(i)
                    zero_cols.add(j)

        # 2) apply
        for i in range(m):
            for j in range(n):
                if i in zero_rows or j in zero_cols:
                    matrix[i][j] = 0

Complexity

• Time Complexity: $O(mn)$
• Space Complexity: $O(m + n)$ (sets for rows and columns)

⭐️ Solution 2: Optimal Version (In-place, O(1) Space)

Idea

We can achieve O(1) extra space by using the matrix itself as a marker board:

• Use the first row to mark which columns should be zeroed
• Use the first column to mark which rows should be zeroed
• But we must preserve whether the first row or first column originally contained any zero, because those cells will be overwritten as markers.
  • firstRowZero: whether row 0 originally has a zero
  • firstColZero: whether col 0 originally has a zero

Steps

1. Scan first row and first column to set firstRowZero, firstColZero
2. For each cell (i, j) (excluding first row/col), if it is 0, mark:
   • matrix[i][0] = 0 (row marker)
   • matrix[0][j] = 0 (col marker)
3. For each inner cell (i, j), set it to 0 if its row or column is marked
4. Finally, zero out the first row/col if firstRowZero / firstColZero is true

Code

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])

        # 1) check whether first row / first col originally contain zero
        firstRowZero = any(matrix[0][j] == 0 for j in range(n))
        firstColZero = any(matrix[i][0] == 0 for i in range(m))

        # 2) use first row/col as markers
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0

        # 3) apply markers to inner cells
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0

        # 4) zero out first row/col if needed
        if firstRowZero:
            for j in range(n):
                matrix[0][j] = 0

        if firstColZero:
            for i in range(m):
                matrix[i][0] = 0

Complexity

• Time Complexity: $O(mn)$
• Space Complexity: $O(1)$ (only constant extra variables)