Algorithm

Set Matrix Zeroes

Arrays & Strings Pattern

Set Matrix Zeroes

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0's. You must do it in place.

CONSTRAINTS
  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -2³¹ <= matrix[i][j] <= 2³¹ - 1
EXAMPLE 1
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
The 0 at (1,1) marks row 1 and col 1 for zeroing. Pass 2 then fills them.
EXAMPLE 2
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]]
Zeroes at (0,0) and (0,3) trigger multiple row and column zeroings.
What should I return if the matrix is already filled with zeros?
The matrix would remain unchanged since all rows and columns are already zero. Your algorithm should handle this efficiently by not performing redundant writes.
Is the matrix always square, or can it be rectangular?
The matrix can be rectangular (M x N). Your solution must handle cases where the number of rows is different from the number of columns.
Should I return a new matrix or modify the input directly?
The requirement is to modify the matrix strictly in-place. Do not return a new 2D array.

If a cell in a matrix is zero, its entire row and column must also become zero. The challenge is that as you set new cells to zero, you risk losing information about where the original zeros were, potentially causing a chain reaction that zeroes out the entire grid.

Row and Column Flags (O(M + N) space)

The easiest way to avoid "zero pollution" is to record the locations of original zeros first. We use two separate boolean arrays to keep track of which rows and which columns must eventually be zeroed.

python
rows_to_zero = [False] * m
cols_to_zero = [False] * n

for i in range(m):
    for j in range(n):
        if matrix[i][j] == 0:
            rows_to_zero[i] = True
            cols_to_zero[j] = True

for i in range(m):
    for j in range(n):
        if rows_to_zero[i] or cols_to_zero[j]:
            matrix[i][j] = 0
2. The Insight: Boundary Markers

Using extra boolean arrays takes O(M+N) space. The core insight is that we don't need external arrays if we can repurpose the first row and first column of the matrix itself as our marker arrays. We just need to handle the overlap at the top-left corner carefully.

Use Boundaries as Memory (O(1) space)

Instead of creating extra arrays, we use the matrix's own "headlines":
1. Pass 1 (Record): If cell (i, j) is 0, mark the first cell of that row and the first cell of that column as 0.
2. Pass 2 (Execute): Use those markers to zero the internal matrix.

python
m, n = len(matrix), len(matrix[0])
first_col_zero = False

# 1. Record zeros into head row/column
for i in range(m):
    if matrix[i][0] == 0: first_col_zero = True
    for j in range(1, n):
        if matrix[i][j] == 0:
            matrix[i][0] = 0
            matrix[0][j] = 0

# 2. Use recorded marks to zero the internal matrix
for i in range(m - 1, -1, -1):
    for j in range(n - 1, 0, -1):
        if matrix[i][0] == 0 or matrix[0][j] == 0:
            matrix[i][j] = 0
    if first_col_zero:
        matrix[i][0] = 0
Worked Example:[[1, 1, 1], [1, 0, 1], [1, 1, 1]]
1
0
1
0
0
1
1
1
1
We perform our first pass to scan for original zeros. When we find one, we use the first cell of its row and column as flags, setting those header cells to 0.
1
0
1
0
0
0
1
0
1
We perform our second pass to zero out all internal cells whose header row or header column has been marked with a 0, completing the in-place update.
Interactive Strategy Visualization

State Matrix Check-Sheet

In-place Indicator Mapping
1
1
1
1
0
1
1
1
1

Scanning matrix for zeroes. Found a 0 at (Row 1, Col 1).

Memory Trick

Instead of an extra O(M+N) array, we use the matrix's own cell [0][0] and the first row/column to store whether that row or col should be zeroed.

Complexity

Time: O(M*N) for two passes. Space: O(1) constant extra space. This demonstrates mastery of bit-flag like optimizations in matrices.

O(M*N) Space
→
O(M+N) Space
→
O(1) Space (Markers)