LeetCode 73 - Set Matrix Zeroes
The problem gives us a two dimensional matrix of integers with m rows and n columns. We must modify the matrix in place so that whenever a cell contains 0, every element in that cell's entire row and entire column also becomes 0.
Difficulty: 🟡 Medium
Topics: Array, Hash Table, Matrix
Solution
LeetCode 73, Set Matrix Zeroes
Problem Understanding
The problem gives us a two dimensional matrix of integers with m rows and n columns. We must modify the matrix in place so that whenever a cell contains 0, every element in that cell's entire row and entire column also becomes 0.
The important detail is that the operation must happen simultaneously from the perspective of the original matrix state. If we immediately start writing zeroes into the matrix while scanning it, we may accidentally create new zeroes that incorrectly affect additional rows and columns.
For example, suppose we see a zero at position (1, 1) and immediately zero out row 1 and column 1. Later, when scanning the matrix, we encounter one of the newly written zeroes and incorrectly assume it existed in the original input. That would spread zeroes farther than intended.
The phrase "in place" means we should avoid allocating another matrix of the same size. The follow up section pushes us toward a constant extra space solution.
The constraints are relatively small, at most 200 x 200, so even an O(mn) or O(m + n) auxiliary structure would fit comfortably in memory. Still, the optimal solution achieves constant extra space while maintaining linear traversal time.
Several edge cases are important:
- A zero may appear in the first row or first column, which becomes tricky because the optimal solution uses those areas as markers.
- The matrix may already contain all zeroes.
- The matrix may contain no zeroes at all.
- A single row or single column matrix can expose indexing mistakes.
- Multiple zeroes may overlap in their affected rows and columns.
Understanding how to preserve the original zero information while modifying the matrix is the core challenge.
Approaches
Brute Force Approach
The most straightforward idea is to create another matrix or maintain a separate record of which cells should become zero.
We first scan the entire matrix and record every row index and column index that contains a zero. After that, we make another pass through the matrix. If a cell belongs to a marked row or marked column, we set it to zero.
This approach is correct because the first pass captures all original zero locations before any modifications occur. The second pass then applies the transformation consistently.
A naive brute force variant could even copy the entire matrix and perform updates based on the copy. That works, but it wastes O(mn) extra space.
A better improvement uses two sets or boolean arrays:
- One structure stores rows that must become zero.
- Another structure stores columns that must become zero.
This reduces extra memory to O(m + n).
Optimal Approach
The key observation is that the matrix itself can store the marker information.
Instead of allocating separate row and column arrays, we can use:
- The first cell of each row to indicate whether that row should become zero.
- The first cell of each column to indicate whether that column should become zero.
For example:
matrix[i][0] == 0means rowishould be zeroed.matrix[0][j] == 0means columnjshould be zeroed.
This cleverly reuses existing space.
The complication is that the first row and first column now serve two purposes:
- They contain actual matrix values.
- They also act as marker storage.
To avoid losing information, we separately track:
- Whether the first row originally contained a zero.
- Whether the first column originally contained a zero.
After all markers are placed, we use them to zero the appropriate cells, then finally handle the first row and first column separately.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(mn) | O(m + n) | Uses separate storage for rows and columns containing zeroes |
| Optimal | O(mn) | O(1) | Uses first row and first column as in place markers |
Algorithm Walkthrough
- Determine whether the first row originally contains any zero.
We scan every column in row 0. If any value is zero, we store this information in a boolean variable such as first_row_zero.
This step is necessary because later we will overwrite cells in the first row with marker values. 2. Determine whether the first column originally contains any zero.
We scan every row in column 0. If any value is zero, we store this information in another boolean variable such as first_col_zero.
This preserves the original state of the first column before it becomes marker storage. 3. Use the first row and first column as markers.
Starting from cell (1, 1), we scan the rest of the matrix.
Whenever we encounter a zero at (i, j):
- Set
matrix[i][0] = 0 - Set
matrix[0][j] = 0
This records that row i and column j must eventually become zero.
4. Zero out rows based on row markers.
For every row i from 1 to m - 1:
- If
matrix[i][0] == 0, set every cell in that row to zero.
We skip row 0 because it still contains marker information.
5. Zero out columns based on column markers.
For every column j from 1 to n - 1:
- If
matrix[0][j] == 0, set every cell in that column to zero.
Again, we skip column 0 because it still stores marker information.
6. Handle the first row.
If first_row_zero is true, set every cell in row 0 to zero.
7. Handle the first column.
If first_col_zero is true, set every cell in column 0 to zero.
Why it works
The algorithm maintains an important invariant:
- Before any row or column is zeroed, the first row and first column accurately store which rows and columns must become zero.
Because the marker phase happens before any large scale modifications, no information is lost. The separate boolean variables preserve the original state of the first row and first column, preventing conflicts between marker storage and actual transformation logic.
Every row and column that originally contained a zero is marked exactly once, and every marked row or column is eventually zeroed.
Python Solution
from typing import List
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
rows = len(matrix)
cols = len(matrix[0])
first_row_zero = False
first_col_zero = False
# Check whether first row contains a zero
for col in range(cols):
if matrix[0][col] == 0:
first_row_zero = True
break
# Check whether first column contains a zero
for row in range(rows):
if matrix[row][0] == 0:
first_col_zero = True
break
# Use first row and first column as markers
for row in range(1, rows):
for col in range(1, cols):
if matrix[row][col] == 0:
matrix[row][0] = 0
matrix[0][col] = 0
# Zero out marked rows
for row in range(1, rows):
if matrix[row][0] == 0:
for col in range(1, cols):
matrix[row][col] = 0
# Zero out marked columns
for col in range(1, cols):
if matrix[0][col] == 0:
for row in range(1, rows):
matrix[row][col] = 0
# Zero out first row if needed
if first_row_zero:
for col in range(cols):
matrix[0][col] = 0
# Zero out first column if needed
if first_col_zero:
for row in range(rows):
matrix[row][0] = 0
The implementation follows the algorithm exactly.
The first section computes the matrix dimensions and initializes two boolean flags. These flags preserve whether the first row or first column originally contained a zero.
The next two loops scan the first row and first column separately. This must happen before marker placement, otherwise we could not distinguish original zeroes from marker zeroes.
The marker phase starts from index 1 for both rows and columns. Whenever a zero is found, the corresponding row marker and column marker are written into the matrix itself.
After all markers are established, the algorithm performs the transformation in two passes:
- One pass zeroes rows based on first column markers.
- Another pass zeroes columns based on first row markers.
Finally, the algorithm applies the saved first row and first column information using the boolean flags.
Because all modifications happen directly inside the original matrix, the solution satisfies the in place requirement.
Go Solution
func setZeroes(matrix [][]int) {
rows := len(matrix)
cols := len(matrix[0])
firstRowZero := false
firstColZero := false
// Check first row
for col := 0; col < cols; col++ {
if matrix[0][col] == 0 {
firstRowZero = true
break
}
}
// Check first column
for row := 0; row < rows; row++ {
if matrix[row][0] == 0 {
firstColZero = true
break
}
}
// Use first row and column as markers
for row := 1; row < rows; row++ {
for col := 1; col < cols; col++ {
if matrix[row][col] == 0 {
matrix[row][0] = 0
matrix[0][col] = 0
}
}
}
// Zero marked rows
for row := 1; row < rows; row++ {
if matrix[row][0] == 0 {
for col := 1; col < cols; col++ {
matrix[row][col] = 0
}
}
}
// Zero marked columns
for col := 1; col < cols; col++ {
if matrix[0][col] == 0 {
for row := 1; row < rows; row++ {
matrix[row][col] = 0
}
}
}
// Zero first row
if firstRowZero {
for col := 0; col < cols; col++ {
matrix[0][col] = 0
}
}
// Zero first column
if firstColZero {
for row := 0; row < rows; row++ {
matrix[row][0] = 0
}
}
}
The Go implementation is structurally identical to the Python version. Since Go slices already behave like references to underlying arrays, modifying matrix directly updates the original structure in place.
Unlike Python, Go does not require explicit type hints or imports for lists. Integer overflow is not a concern here because the algorithm only compares and assigns values.
The matrix is guaranteed to contain at least one row and one column, so accessing matrix[0] is safe under the problem constraints.
Worked Examples
Example 1
Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Step 1: Check first row
| First Row | Contains Zero |
|---|---|
| [1,1,1] | No |
first_row_zero = False
Step 2: Check first column
| First Column | Contains Zero |
|---|---|
| [1,1,1] | No |
first_col_zero = False
Step 3: Place markers
We scan from (1,1) onward.
At (1,1) we find 0.
Set:
matrix[1][0] = 0matrix[0][1] = 0
Matrix becomes:
| Row Index | Matrix State |
|---|---|
| 0 | [1,0,1] |
| 1 | [0,0,1] |
| 2 | [1,1,1] |
Step 4: Zero marked rows
Row 1 is marked because matrix[1][0] == 0.
Matrix becomes:
| Row Index | Matrix State |
|---|---|
| 0 | [1,0,1] |
| 1 | [0,0,0] |
| 2 | [1,1,1] |
Step 5: Zero marked columns
Column 1 is marked because matrix[0][1] == 0.
Matrix becomes:
| Row Index | Matrix State |
|---|---|
| 0 | [1,0,1] |
| 1 | [0,0,0] |
| 2 | [1,0,1] |
Step 6 and 7
Neither the first row nor first column originally contained a zero, so no further changes occur.
Final result:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
Example 2
Input:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Step 1: Check first row
The first row already contains zeroes.
first_row_zero = True
Step 2: Check first column
The first column contains a zero at (0,0).
first_col_zero = True
Step 3: Place markers
Scanning the inner matrix finds no additional zeroes.
Current matrix:
| Row Index | Matrix State |
|---|---|
| 0 | [0,1,2,0] |
| 1 | [3,4,5,2] |
| 2 | [1,3,1,5] |
The existing zeroes in the first row already act as markers:
- Column
0marked - Column
3marked
Step 4: Zero marked rows
No additional row markers exist.
Step 5: Zero marked columns
Columns 0 and 3 become zero.
Matrix becomes:
| Row Index | Matrix State |
|---|---|
| 0 | [0,1,2,0] |
| 1 | [0,4,5,0] |
| 2 | [0,3,1,0] |
Step 6: Zero first row
Since first_row_zero is true:
| Row Index | Matrix State |
|---|---|
| 0 | [0,0,0,0] |
| 1 | [0,4,5,0] |
| 2 | [0,3,1,0] |
Step 7: Zero first column
The first column is already zero.
Final result:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(mn) | Every cell is visited a constant number of times |
| Space | O(1) | Only two boolean variables are used outside the input matrix |
The algorithm performs several matrix scans, but each scan is linear in the number of cells. Since constants are ignored in asymptotic analysis, the total runtime remains O(mn).
The solution uses constant auxiliary space because marker information is stored directly inside the matrix rather than in external arrays or sets.
Test Cases
from typing import List
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
rows = len(matrix)
cols = len(matrix[0])
first_row_zero = False
first_col_zero = False
for col in range(cols):
if matrix[0][col] == 0:
first_row_zero = True
break
for row in range(rows):
if matrix[row][0] == 0:
first_col_zero = True
break
for row in range(1, rows):
for col in range(1, cols):
if matrix[row][col] == 0:
matrix[row][0] = 0
matrix[0][col] = 0
for row in range(1, rows):
if matrix[row][0] == 0:
for col in range(1, cols):
matrix[row][col] = 0
for col in range(1, cols):
if matrix[0][col] == 0:
for row in range(1, rows):
matrix[row][col] = 0
if first_row_zero:
for col in range(cols):
matrix[0][col] = 0
if first_col_zero:
for row in range(rows):
matrix[row][0] = 0
solution = Solution()
# Example 1
matrix = [[1,1,1],[1,0,1],[1,1,1]]
solution.setZeroes(matrix)
assert matrix == [[1,0,1],[0,0,0],[1,0,1]] # middle zero
# Example 2
matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
solution.setZeroes(matrix)
assert matrix == [[0,0,0,0],[0,4,5,0],[0,3,1,0]] # first row and column zeroes
# Single element non-zero
matrix = [[5]]
solution.setZeroes(matrix)
assert matrix == [[5]] # unchanged matrix
# Single element zero
matrix = [[0]]
solution.setZeroes(matrix)
assert matrix == [[0]] # remains zero
# Single row
matrix = [[1,0,3,4]]
solution.setZeroes(matrix)
assert matrix == [[0,0,0,0]] # entire row becomes zero
# Single column
matrix = [[1],[0],[3]]
solution.setZeroes(matrix)
assert matrix == [[0],[0],[0]] # entire column becomes zero
# Multiple zeroes
matrix = [
[1,0,3],
[4,5,6],
[0,8,9]
]
solution.setZeroes(matrix)
assert matrix == [
[0,0,0],
[0,0,6],
[0,0,0]
] # overlapping row and column updates
# No zeroes
matrix = [
[1,2],
[3,4]
]
solution.setZeroes(matrix)
assert matrix == [
[1,2],
[3,4]
] # matrix unchanged
# Entire matrix already zero
matrix = [
[0,0],
[0,0]
]
solution.setZeroes(matrix)
assert matrix == [
[0,0],
[0,0]
] # stable all-zero matrix
| Test | Why |
|---|---|
[[1,1,1],[1,0,1],[1,1,1]] |
Standard middle zero case |
[[0,1,2,0],[3,4,5,2],[1,3,1,5]] |
Validates first row and first column handling |
[[5]] |
Smallest non-zero matrix |
[[0]] |
Smallest zero matrix |
[[1,0,3,4]] |
Single row edge case |
[[1],[0],[3]] |
Single column edge case |
| Multiple zeroes matrix | Tests overlapping propagation |
| Matrix with no zeroes | Ensures no accidental modification |
| All zero matrix | Confirms stability of repeated zero operations |
Edge Cases
Zero in the First Row
The first row is used as column marker storage in the optimal solution. If the first row originally contains a zero, we cannot distinguish whether a zero in the first row is an original value or merely a marker unless we store that information separately.
The implementation handles this with the first_row_zero boolean variable, computed before marker placement begins.
Zero in the First Column
The same issue exists for the first column because it stores row markers. If the first column originally contains a zero, the algorithm must remember this independently.
The first_col_zero variable preserves that information so the first column can be zeroed correctly at the end.
Single Row or Single Column Matrices
Matrices such as [[1,0,3]] or [[1],[0],[3]] can expose indexing mistakes because the inner traversal from (1,1) may never execute.
The implementation safely handles these cases because all loops use the matrix dimensions dynamically, and the first row and first column logic still correctly applies the transformation.
Multiple Overlapping Zeroes
When several zeroes affect overlapping rows and columns, careless implementations may repeatedly overwrite markers or accidentally propagate newly written zeroes.
This algorithm avoids that issue because all marker placement occurs before any row or column is fully zeroed. The original zero information remains intact throughout the marking phase.