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 — Matrix Traversal

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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

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…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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

Python

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

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.

3

Zero First Column if Marked

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

4

Zero First Row if Marked by Separate Flag

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

3 more steps with full analysis available on Pro.

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.

Full line-by-line criticality + rationale for all 20 lines available on Pro.

Test Your Understanding

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

See the answer with Pro.

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`