Set Matrix Zeroes
Set Matrix Zeroes is a medium arrays & hashing problem solved with the in-place transformations pattern.
The best approach, optimal (first row and column as markers), runs in O(m · n) time and O(1) space.
Below are 2 approaches in Java, from brute force (marker sets) up.
Problem
Given an m × n integer matrix, if a cell is 0, set its entire row and column to 0. Do it in place.
Follow-up: can you use constant extra space?
Examples
Example 1
- Input
matrix = [[1,2,3],[4,0,6],[7,8,9]]- Output
[[1,0,3],[0,0,0],[7,0,9]]
Example 2
- Input
matrix = [[0,1],[1,1]]- Output
[[0,0],[0,1]]
Constraints
1 <= m, n <= 200- Modify the matrix in place.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| Brute force (marker sets) | O(m · n) | O(m + n) |
| Optimal (first row and column as markers) | O(m · n) | O(1) |
1Brute force (marker sets)
O(m · n)O(m + n)Record which rows and columns contain a zero, then zero them in a second pass. Using sets avoids reacting to zeros you created.
- Scan and add zero rows and columns to two boolean arrays.
- Zero every cell whose row or column is marked.
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean[] row = new boolean[m], col = new boolean[n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (matrix[i][j] == 0) { row[i] = true; col[j] = true; }
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (row[i] || col[j]) matrix[i][j] = 0;
}
}2Optimal (first row and column as markers)
O(m · n)O(1)Use matrix[i][0] and matrix[0][j] as the row and column markers. The first row and first column need their own flags, since their markers overlap at matrix[0][0]. Zero the inner cells first, then the first row and column last.
- Record whether the first row and first column had any zero.
- For inner cells with a zero, set matrix[i][0] = matrix[0][j] = 0.
- Zero inner cells whose row or column marker is 0.
- Finally zero the first row and first column if their flags are set.
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean firstRow = false, firstCol = false;
for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRow = true;
for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstCol = true;
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; }
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
if (firstRow) for (int j = 0; j < n; j++) matrix[0][j] = 0;
if (firstCol) for (int i = 0; i < m; i++) matrix[i][0] = 0;
}
}Edge cases to test
- A zero in the first row or first column
- Zeros created by the algorithm must not trigger more zeroing
Hints
Hint 1
Can the first row and first column act as the markers?
FAQ
What is the best time complexity for Set Matrix Zeroes?
Optimal (first row and column as markers) runs in O(m · n) time and O(1) extra space.
Which pattern does Set Matrix Zeroes use?
It is a arrays & hashing problem that uses the in-place transformations pattern. Other problems with the same pattern: Find All Duplicates in an Array.
Is there a brute force solution for Set Matrix Zeroes?
Yes. Brute force (marker sets) takes O(m · n) time and O(m + n) space. Record which rows and columns contain a zero, then zero them in a second pass.
Which edge cases should I test for Set Matrix Zeroes?
A zero in the first row or first column; Zeros created by the algorithm must not trigger more zeroing.