Approach Summary
Use first row and column as markers. Mark zero locations, then zero out rows/columns accordingly.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Extra Space (Row & Column Sets) | O(M * N) | O(M + N) | Uses two auxiliary boolean arrays or hash sets to record zeroed rows and columns before zeroing the matrix. |
| 2 Approach 2: In-Place Constant Auxiliary Space (Optimal) | O(M * N) | O(1) | Stores row and column zero flags directly in the first row and first column of the input matrix, with two boolean flags for row 0 and col 0. |
Step 1: Baseline
Approach 1: Extra Space (Row & Column Sets)
Time: O(M * N)
Space: O(M + N)
1. Create a boolean array `zeroRows[M]` and `zeroCols[N]`. 2. Iterate through all cells `(i, j)`. If `matrix[i][j] == 0`, mark `zeroRows[i] = true` and `zeroCols[j] = true`. 3. Iterate through all cells a second time. If `zeroRows[i]` or `zeroCols[j]` is true, set `matrix[i][j] = 0`. 4. Simple and effective, but uses O(M + N) extra space.
Approach 1: Extra Space (Row & Column Sets) Implementation
Approach 1: Extra Space (Row & Column Sets)
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean[] rows = new boolean[m], cols = new boolean[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
rows[i] = true;
cols[j] = true;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rows[i] || cols[j]) matrix[i][j] = 0;
}
}
}
}class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<bool> rows(m, false), cols(n, false);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
rows[i] = true;
cols[j] = true;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rows[i] || cols[j]) matrix[i][j] = 0;
}
}
}
};class Solution:
def setZeroes(self, matrix: list[list[int]]) -> None:
m, n = len(matrix), len(matrix[0])
rows, cols = set(), set()
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
rows.add(i)
cols.add(j)
for i in range(m):
for j in range(n):
if i in rows or j in cols:
matrix[i][j] = 0var setZeroes = function(matrix) {
const m = matrix.length, n = matrix[0].length;
const rows = new Set(), cols = new Set();
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 0) {
rows.add(i);
cols.add(j);
}
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (rows.has(i) || cols.has(j)) {
matrix[i][j] = 0;
}
}
}
}; Step 2: Most Optimized
Approach 2: In-Place Constant Auxiliary Space (Optimal)
Time: O(M * N)
Space: O(1)
1. Use flags `x` (or `firstColZero`) and `y` (or `firstRowZero`) to record whether col 0 and row 0 initially contain any zero. 2. Iterate through `1 <= i < M` and `1 <= j < N`. If `matrix[i][j] == 0`, set `matrix[i][0] = 0` and `matrix[0][j] = 0`. 3. Using those markers, zero out all inner cells where `matrix[i][0] == 0` or `matrix[0][j] == 0`. 4. Finally, if `x == 0`, zero out the entire first column. If `y == 0`, zero out the entire first row. 5. Consumes strictly O(1) auxiliary space.
Approach 2: In-Place Constant Auxiliary Space (Optimal) Implementation
Approach 2: In-Place Constant Auxiliary Space (Optimal)
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean row0 = false, col0 = false;
for (int j = 0; j < n; j++) if (matrix[0][j] == 0) row0 = true;
for (int i = 0; i < m; i++) if (matrix[i][0] == 0) col0 = 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 (row0) for (int j = 0; j < n; j++) matrix[0][j] = 0;
if (col0) for (int i = 0; i < m; i++) matrix[i][0] = 0;
}
}class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool row0 = false, col0 = false;
for (int j = 0; j < n; j++) if (matrix[0][j] == 0) row0 = true;
for (int i = 0; i < m; i++) if (matrix[i][0] == 0) col0 = 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 (row0) for (int j = 0; j < n; j++) matrix[0][j] = 0;
if (col0) for (int i = 0; i < m; i++) matrix[i][0] = 0;
}
};class Solution:
def setZeroes(self, matrix: list[list[int]]) -> None:
m, n = len(matrix), len(matrix[0])
first_row_zero = any(matrix[0][j] == 0 for j in range(n))
first_col_zero = any(matrix[i][0] == 0 for i in range(m))
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = matrix[0][j] = 0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if first_row_zero:
for j in range(n): matrix[0][j] = 0
if first_col_zero:
for i in range(m): matrix[i][0] = 0var setZeroes = function(matrix) {
const m = matrix.length, n = matrix[0].length;
let row0 = false, col0 = false;
for (let j = 0; j < n; j++) if (matrix[0][j] === 0) row0 = true;
for (let i = 0; i < m; i++) if (matrix[i][0] === 0) col0 = true;
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][j] === 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][0] === 0 || matrix[0][j] === 0) matrix[i][j] = 0;
}
}
if (row0) for (let j = 0; j < n; j++) matrix[0][j] = 0;
if (col0) for (let i = 0; i < m; i++) matrix[i][0] = 0;
};Edge Cases to Watch
- Single row matrix [[1, 0, 3]] — row becomes all zeros
- Single column matrix [[1], [0], [3]] — column becomes all zeros
- Matrix[0][0] is originally 0 — correctly zeros out both row 0 and col 0 without corrupting other flags
- Matrix with no zeros — remains completely unmodified
- Matrix that is already all zeros — remains all zeros without redundant work
Algorithmic Pattern
View Pattern Guide →
Master the Matrix Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Matrix pattern.
How to Recognize This Pattern
- Zero out rows and columns in-place
- Use first row/col as flags
Complexity Analysis
Time Complexity
O(m × n)
Space Complexity
O(1)
Tags
Array Matrix
Frequently Asked Questions
What is the optimal time and space complexity for Set Matrix Zeroes?
The optimal solution for Set Matrix Zeroes achieves O(m × n) runtime complexity and requires O(1) auxiliary space. Time Complexity is O(M * N) where M is the number of rows and N is the number of columns. We perform two full passes over the matrix cells. Space Complexity is O(1) auxiliary space because state is tracked in-place inside the first row and first column of the input matrix, with only a few primitive variables.
How do I identify that Set Matrix Zeroes requires the Matrix pattern?
In technical interviews, look for key problem signals: Zero out rows and columns in-place; Use first row/col as flags. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Matrix strategy.
What critical edge cases must be handled in Set Matrix Zeroes?
Essential edge cases to verify include: Single row matrix [[1, 0, 3]] — row becomes all zeros; Single column matrix [[1], [0], [3]] — column becomes all zeros; Matrix[0][0] is originally 0 — correctly zeros out both row 0 and col 0 without corrupting other flags; Matrix with no zeros — remains completely unmodified. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Set Matrix Zeroes?
Set Matrix Zeroes is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Microsoft, Apple.