LeetCode 73: Set Matrix Zeroes Solution in Python Explained

Problem Statement

LeetCode 73, Set Matrix Zeroes, is a medium-level problem where you’re given an (m \times n) integer matrix matrix. Your task is to modify it in-place such that if any cell contains a 0, the entire row and column containing that 0 are set to 0. The solution must use O(1) extra space, meaning no additional arrays beyond a few variables.

Constraints

  • m == matrix.length: Number of rows.
  • n == matrix[i].length: Number of columns.
  • 1 <= m, n <= 200: Matrix dimensions are between 1 and 200.
  • -2^31 <= matrix[i][j] <= 2^31 - 1: Cell values are 32-bit integers.

Example

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Explanation: Zero at (1,1) sets row 1 and column 1 to 0.

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Explanation: Zeros at (0,0) and (0,3) set rows 0, 1, 2 and columns 0, 3 to 0.

Input: matrix = [[1]]
Output: [[1]]
Explanation: No zeros, matrix unchanged.

Understanding the Problem

How do you solve LeetCode 73: Set Matrix Zeroes in Python? For matrix = [[1,1,1],[1,0,1],[1,1,1]], set the row and column of the 0 at (1,1) to 0, resulting in [[1,0,1],[0,0,0],[1,0,1]]. We need an in-place solution with O(1) space, avoiding extra arrays. We’ll explore two approaches: an In-Place with Markers Solution (optimal and primary) and an Alternative with Extra Space (intuitive but not O(1)). The in-place method runs in O(m * n) time with O(1) space, using the matrix itself to mark rows and columns.

Solution 1: In-Place with Markers Approach (Primary)

Explanation

Use the first row and first column as markers to indicate which rows and columns need to be zeroed. Scan the matrix to mark these rows and columns, then use the markers to set the appropriate cells to 0. Handle the first row and column separately to avoid overwriting markers prematurely.

Here’s a flow for [[1,1,1],[1,0,1],[1,1,1]]:

Step 1: Mark 0 at (1,1) -> first_row[1]=0, first_col[1]=0
Step 2: Use markers to set rows 0,2 and cols 0,2 -> [[1,0,1],[0,0,0],[1,0,1]]
Step 3: Set first row and column based on initial flags
Result: [[1,0,1],[0,0,0],[1,0,1]]
  1. Check First Row and Column.
  • Record if they contain zeros initially.
  1. Mark Zeros.
  • Use first row and column as flags for other zeros.
  1. Set Rows and Columns.
  • Zero out based on markers, excluding first row/column.
  1. Handle First Row and Column.
  • Zero them if flagged.
  1. Modify In-Place.

Step-by-Step Example

Example 1: matrix = [[1,1,1],[1,0,1],[1,1,1]]

We need [[1,0,1],[0,0,0],[1,0,1]].

  • Goal: Set rows and columns of zeros to 0 in-place.
  • Result for Reference: [[1,0,1],[0,0,0],[1,0,1]].
  • Start: matrix = [[1,1,1],[1,0,1],[1,1,1]], m = 3, n = 3.
  • Step 1: Check first row and column.
    • First row [1,1,1], row_zero = False.
    • First column [1,1,1], col_zero = False.
  • Step 2: Mark zeros.
    • (1,1) = 0, set matrix[1][0] = 0, matrix[0][1] = 0.
    • Matrix = [[1,0,1],[0,0,1],[1,1,1]].
  • Step 3: Set rows (skip first).
    • Row 1: matrix[1][1] = 0 (already), matrix[1][2] = 0.
    • Row 2: matrix[2][1] = 0 (due to marker 0 in col 1).
    • Matrix = [[1,0,1],[0,0,0],[1,0,1]].
  • Step 4: Set columns (skip first).
    • Col 1: matrix[0][1] = 0 (already), matrix[2][1] = 0 (already).
    • Matrix unchanged: [[1,0,1],[0,0,0],[1,0,1]].
  • Step 5: First row and column.
    • row_zero = False, col_zero = False, no change.
  • Finish: Matrix = [[1,0,1],[0,0,0],[1,0,1]].

Example 2: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

We need [[0,0,0,0],[0,4,5,0],[0,3,1,0]].

  • Start: m = 3, n = 4.
  • Step 1: Check.
    • First row [0,1,2,0], row_zero = True.
    • First column [0,3,1], col_zero = True.
  • Step 2: Mark zeros.
    • (0,0), (0,3) already marked in first row/col.
    • Matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]].
  • Step 3: Set rows and cols using markers.
    • After marking and setting: [[0,0,0,0],[0,4,5,0],[0,3,1,0]].
  • Finish: Matrix = [[0,0,0,0],[0,4,5,0],[0,3,1,0]].

How the Code Works (In-Place with Markers)

Here’s the Python code with line-by-line explanation:

def setZeroes(matrix: list[list[int]]) -> None:
    # Line 1: Get dimensions
    m, n = len(matrix), len(matrix[0])

    # Line 2: Check if first row and column have zeros
    row_zero = 0 in matrix[0]
    col_zero = 0 in [matrix[i][0] for i in range(m)]

    # Line 3: Mark zeros using first row and column
    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

    # Line 4: Set rows based on first column marker
    for i in range(1, m):
        if matrix[i][0] == 0:
            for j in range(1, n):
                matrix[i][j] = 0

    # Line 5: Set columns based on first row marker
    for j in range(1, n):
        if matrix[0][j] == 0:
            for i in range(1, m):
                matrix[i][j] = 0

    # Line 6: Set first row and column if needed
    if row_zero:
        for j in range(n):
            matrix[0][j] = 0
    if col_zero:
        for i in range(m):
            matrix[i][0] = 0

Alternative: Extra Space Approach

Explanation

Use two sets to track rows and columns containing zeros, then iterate again to set those rows and columns to 0. This uses O(m + n) space, not meeting the O(1) requirement, but is intuitive for understanding.

  1. Track Zeros.
  • Store row and column indices of zeros.
  1. Set Rows and Columns.
  • Zero out marked rows and columns.
  1. Modify Matrix.

Step-by-Step Example (Alternative)

For [[1,1,1],[1,0,1],[1,1,1]]:

  • Start: zero_rows = set(), zero_cols = set().
  • Step 1: Scan for zeros.
    • (1,1) = 0, zero_rows = {1}, zero_cols = {1}.
  • Step 2: Set rows and columns.
    • Row 1: [0,0,0].
    • Col 1: [1,0,1] -> [0,0,0], [1,0,1].
  • Finish: Matrix = [[1,0,1],[0,0,0],[1,0,1]].

How the Code Works (Extra Space)

def setZeroesExtra(matrix: list[list[int]]) -> None:
    # Line 1: Initialize sets for zero rows and columns
    m, n = len(matrix), len(matrix[0])
    zero_rows = set()
    zero_cols = set()

    # Line 2: Mark rows and columns with zeros
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                zero_rows.add(i)
                zero_cols.add(j)

    # Line 3: Set rows to zero
    for i in zero_rows:
        for j in range(n):
            matrix[i][j] = 0

    # Line 4: Set columns to zero
    for j in zero_cols:
        for i in range(m):
            matrix[i][j] = 0

Complexity

  • In-Place with Markers:
    • Time: O(m * n) – Multiple passes through matrix.
    • Space: O(1) – Only two boolean variables.
  • Extra Space:
    • Time: O(m * n) – Two passes.
    • Space: O(m + n) – Sets for rows and columns.

Efficiency Notes

In-Place with Markers is O(m * n) time and O(1) space, meeting LeetCode 73’s requirement perfectly. Extra Space is O(m * n) time and O(m + n) space, easier to understand but not O(1), making it a teaching tool rather than the optimal solution.

Key Insights

Tips to master LeetCode 73:

  • In-Place Marking: Use matrix itself as storage.
  • First Row/Col: Handle separately to preserve markers.
  • Two Passes: Mark then set for accuracy.

Additional Example

For matrix = [[1,0],[0,1]]:

  • Goal: [[0,0],[0,0]].
  • In-Place: Mark, set -> [[0,0],[0,0]].
  • Result: [[0,0],[0,0]].

Edge Cases

  • Single Cell: [[0]] – Return [[0]].
  • No Zeros: [[1,2]] – Unchanged.
  • All Zeros: [[0,0],[0,0]] – Return [[0,0],[0,0]].

Final Thoughts

The In-Place with Markers solution is a brilliant pick for LeetCode 73 in Python—clever, efficient, and space-compliant. For a related challenge, try LeetCode 72: Edit Distance to switch to DP! Ready to zero out? Solve LeetCode 73 on LeetCode now and test it with [[1,1,1],[1,0,1],[1,1,1]] or [[0,1,2,0],[3,4,5,2]] to master in-place matrix manipulation. Dive in and clear those rows and columns!