What pattern does Set Matrix Zeroes use?

The Pattern: Matrix Traversal (In-Place State Encoding) The Heuristic: Use the matrix's first row and column as marker arrays to encode state in-place, avoiding extra space, while carefully preserving their original information with auxiliary flags.

Set Matrix Zeroes - LeetCode Solution

Q: What is the time complexity of Set Matrix Zeroes?

O(m * n). The algorithm performs two full passes over the matrix: one to mark zeros and one to apply zeroing, each touching every element once.

Problem

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0 in-place.

m == matrix.length
n == matrix[0].length
1 ≤ m, n ≤ 200
−2³¹ ≤ matrix[i][j] ≤ 2³¹ - 1

Example

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

Output: [[1,0,1],[0,0,0],[1,0,1]]

The brute-force approach would scan the matrix and record all zero positions, then zero out rows and columns accordingly. This requires extra space proportional to the number of zeros or rows and columns. The optimal approach uses the first row and first column of the matrix itself as markers to record which rows and columns should be zeroed, avoiding extra space. The algorithm first scans the matrix, marking zeros in the first row and column. It also tracks if the first row itself contains any zeros separately. This setup enables zeroing the matrix in a second pass.

Approach

Straightforward Solution

A naive solution uses two sets or arrays to track zero rows and zero columns, then zeroes them in a separate pass. This uses O(m + n) extra space, which is not allowed by the problem constraints.

Core Observation

Setting entire rows and columns to zero based on zero elements requires remembering which rows and columns contain zeros. Using extra space for this is straightforward but not optimal. The key insight is that the first row and first column can serve as in-place markers to record zero presence, saving space.

Path to Optimal

The problem can be optimized by using the first row and first column of the matrix itself as the marker arrays. During the first pass, whenever a zero is found at (r, c), set matrix[0][c] and matrix[r][0] to zero. Because the first row and column are used as markers, a separate boolean variable tracks if the first row itself contains any zero to avoid overwriting its marker role. This approach reduces space complexity to O(1) auxiliary space.

Optimal Approach

Perform two passes: first, scan the matrix to mark zeros in the first row and column and track if the first row has zero. Second, iterate over the matrix (excluding first row and column) and set elements to zero if their row or column marker is zero. Finally, zero out the first column if needed, and zero out the first row if needed based on the boolean flag. This approach modifies the matrix in-place with O(1) extra space and O(m*n) time.

Time

O(m * n)

The algorithm performs two full passes over the matrix: one to mark zeros and one to apply zeroing, each touching every element once.

Space

O(1)

Only a single boolean variable is used to track the first row's zero presence; all other state is encoded in the input matrix itself, meeting the in-place requirement.

Solution

1class Solution:
  def setZeroes(self, matrix: list[list[int]]) -> None:
      ROWS, COLS = len(matrix), len(matrix[0])
      row_zero = False
5
      for r in range(ROWS):
          for c in range(COLS):
              if matrix[r][c] == 0:
                  matrix[0][c] = 0
                  if r > 0:
                      matrix[r][0] = 0
                  else:
                      row_zero = True
      
      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
      
      if matrix[0][0] == 0:
          for r in range(ROWS):
              matrix[r][0] = 0
      
      if row_zero:
          for c in range(COLS):
              matrix[0][c] = 0

Step-by-Step Solution

1

Mark Rows and Columns to be Zeroed Using First Row and Column

3ROWS, COLS = len(matrix), len(matrix[0])
4row_zero = False
6for r in range(ROWS):
  for c in range(COLS):
      if matrix[r][c] == 0:
          matrix[0][c] = 0
          if r > 0:
              matrix[r][0] = 0
          else:
              row_zero = True

Objective

To scan the matrix and mark zero rows and columns by setting the first cell of each corresponding row and column to zero, while tracking if the first row contains zero.

Key Insight

By using the first row and first column as markers, the algorithm encodes which rows and columns must be zeroed without extra space. The separate boolean flag for the first row prevents overwriting its original zero information, which is critical for correctness. This step sets up the in-place state encoding that enables the zeroing in the next phase.

Interview Quick-Check

Core Logic

Mark zero rows and columns by setting matrix[0][c] and matrix[r][0] to zero when a zero is found at (r, c), and track if the first row contains zero separately.

State & Boundaries

Only mark matrix[r][0] if r > 0 to avoid overwriting the first row marker; use a separate boolean for the first row.

Common Pitfalls & Bugs

Failing to track the first row zero separately leads to incorrect zeroing of the first row later.

2

Zero Matrix Cells Based on Markers in First Row and Column

15for 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

Objective

To iterate over the matrix (excluding first row and column) and set cells to zero if their row or column is marked zero in the first row or column.

Key Insight

This step applies the zeroing based on the in-place markers set previously. By skipping the first row and column, the algorithm preserves the marker information until all dependent cells are updated. This separation of concerns ensures correctness and enables efficient in-place modification.

Interview Quick-Check

Core Logic

Set matrix[r][c] to zero if either matrix[0][c] or matrix[r][0] is zero, applying the markers to zero the appropriate cells.

State & Boundaries

Start iteration from row 1 and column 1 to avoid overwriting the first row and column markers prematurely.

Complexity

This pass is O(m*n) and modifies the matrix in-place without extra space.

3

Zero First Column if Marked

20if matrix[0][0] == 0:
21    for r in range(ROWS):
22        matrix[r][0] = 0

Objective

To zero out the entire first column if the top-left cell (matrix[0][0]) is zero, indicating the first column must be zeroed.

Key Insight

The top-left cell serves as the marker for the first column. If it is zero, the entire first column must be zeroed. This step finalizes the zeroing of the first column after all other cells have been processed, preserving the marker information during the previous step.

Interview Quick-Check

Core Logic

Use matrix[0][0] as the marker for zeroing the first column, zeroing it only after other cells are updated.

State & Boundaries

Iterate over all rows to zero the first column when required.

4

Zero First Row if Marked by Separate Flag

24if row_zero:
25    for c in range(COLS):
26        matrix[0][c] = 0

Objective

To zero out the entire first row if the separate boolean flag indicates it originally contained a zero.

Key Insight

Because the first row is used as a marker for columns, its original zero state is tracked separately. This step ensures the first row is zeroed only if it originally contained a zero, preserving correctness while using the first row as a marker.

Interview Quick-Check

Core Logic

Use a separate boolean flag to determine if the first row should be zeroed, avoiding conflicts with its role as a marker.

State & Boundaries

Iterate over all columns to zero the first row when required.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 9 Critical

matrix[0][c] = 0

Mark the column by setting the first row's cell in this column to zero.

Using the first row as a marker for columns encodes zero presence without extra space.

Line 11 Critical

matrix[r][0] = 0

Mark the row by setting the first column's cell in this row to zero.

Using the first column as a marker for rows encodes zero presence without extra space.

Line 17 Critical

if matrix[0][c] == 0 or matrix[r][0] == 0:

Check if the current row or column is marked for zeroing.

If either the first cell of the row or the first cell of the column is zero, the current cell must be zeroed.

Line 18 Critical

matrix[r][c] = 0

Set the current cell to zero based on markers.

This applies the zeroing to all cells in marked rows or columns, completing the in-place transformation.

Line 8 Core

if matrix[r][c] == 0:

Check if the current cell is zero.

Identifying zero cells is the trigger for marking the corresponding row and column for zeroing.

Line 12 Core

else:

Handle the case when the zero is in the first row.

The first row's zero presence is tracked separately to avoid losing marker information.

Line 13 Core

row_zero = True

Set the flag indicating the first row contains a zero.

This flag preserves the original zero state of the first row for later zeroing.

Line 20 Core

if matrix[0][0] == 0:

Check if the first column is marked for zeroing by inspecting the top-left cell.

The top-left cell serves as the marker for the first column's zeroing requirement.

Line 24 Core

if row_zero:

Check if the first row originally contained a zero using the boolean flag.

This flag preserves the original zero state of the first row, enabling correct zeroing after marker usage.

Line 4 Core

row_zero = False

Initialize a boolean flag to track if the first row contains any zero.

This flag preserves the original zero state of the first row, which is necessary because the first row is used as a marker for columns.

Line 10 Core

if r > 0:

Check if the zero is not in the first row.

Avoid overwriting the first row marker when marking rows; handle first row separately.

Line 22 Core

matrix[r][0] = 0

Set the first column cell in the current row to zero.

This completes zeroing of the first column cells when required.

Line 26 Core

matrix[0][c] = 0

Set the first row cell in the current column to zero.

This completes zeroing of the first row cells when required.

Line 21 Standard

for r in range(ROWS):

Iterate over all rows to zero the first column if needed.

This loop applies zeroing to the entire first column based on the marker.

Line 25 Standard

for c in range(COLS):

Iterate over all columns to zero the first row if needed.

This loop applies zeroing to the entire first row based on the flag.

Line 15 Standard

for r in range(1, ROWS):

Iterate over rows starting from the second row.

Skip the first row to preserve marker information during zeroing of other cells.

Line 16 Standard

for c in range(1, COLS):

Iterate over columns starting from the second column.

Skip the first column to preserve marker information during zeroing of other cells.

Line 6 Standard

for r in range(ROWS):

Iterate over each row index.

This loop scans every row to detect zeros and mark rows and columns accordingly.

Line 7 Standard

for c in range(COLS):

Iterate over each column index within the current row.

Nested iteration ensures every cell in the matrix is examined.

Line 3 Basic

ROWS, COLS = len(matrix), len(matrix[0])

Store the number of rows and columns in variables.

Caching the dimensions avoids repeated calls to len() and clarifies boundary conditions for loops.

Test Your Understanding

Why is it necessary to track separately whether the first row contains a zero?

Because the first row is used as a marker for columns, overwriting it during marking would lose information about whether the first row itself originally contained a zero. A separate boolean flag preserves this information to correctly zero the first row at the end.

Don't just read it. Drill it.

Reconstruct Set Matrix Zeroes from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Set Matrix Zeroes drill

or drill a free problem

1	`class Solution:`
2	`def setZeroes(self, matrix: list[list[int]]) -> None:`
3	`ROWS, COLS = len(matrix), len(matrix[0])`
4	`row_zero = False`
5
6	`for r in range(ROWS):`
7	`for c in range(COLS):`
8	`if matrix[r][c] == 0:`
9	`matrix[0][c] = 0`
10	`if r > 0:`
11	`matrix[r][0] = 0`
12	`else:`
13	`row_zero = True`
14
15	`for r in range(1, ROWS):`
16	`for c in range(1, COLS):`
17	`if matrix[0][c] == 0 or matrix[r][0] == 0:`
18	`matrix[r][c] = 0`
19
20	`if matrix[0][0] == 0:`
21	`for r in range(ROWS):`
22	`matrix[r][0] = 0`
23
24	`if row_zero:`
25	`for c in range(COLS):`
26	`matrix[0][c] = 0`

3	`ROWS, COLS = len(matrix), len(matrix[0])`
4	`row_zero = False`
6	`for r in range(ROWS):`
7	`for c in range(COLS):`
8	`if matrix[r][c] == 0:`
9	`matrix[0][c] = 0`
10	`if r > 0:`
11	`matrix[r][0] = 0`
12	`else:`
13	`row_zero = True`

Problem

Example

Approach

Solution

Step-by-Step Solution

Mark Rows and Columns to be Zeroed Using First Row and Column

Zero Matrix Cells Based on Markers in First Row and Column

Zero First Column if Marked

Zero First Row if Marked by Separate Flag

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.