Set Matrix Zeroes
Description
You are given an m × n integer matrix. Your task is to modify the matrix so that whenever any element is 0, its entire row and its entire column are all set to 0.
You must perform this operation in place, meaning you should modify the original matrix directly rather than creating a new one.
For example, if a matrix has a 0 at row 1, column 1, then every cell in row 1 must become 0 and every cell in column 1 must become 0, regardless of their original values. If there are multiple 0s in the original matrix, all of their corresponding rows and columns must be zeroed out.
Examples
Example 1
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Explanation: The only 0 in the original matrix is at position [1][1]. Therefore, the entire row 1 becomes [0,0,0] and the entire column 1 becomes [0,0,0]. All other cells not in row 1 or column 1 remain unchanged.
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]]
Explanation: The original matrix has 0s at positions [0][0] and [0][3]. Row 0 is entirely zeroed out. Column 0 and column 3 are entirely zeroed out. Cells not in row 0, column 0, or column 3 keep their original values.
Example 3
Input: matrix = [[1,2,3],[4,0,6],[7,8,9]]
Output: [[1,0,3],[0,0,0],[7,0,9]]
Explanation: There is a single 0 at [1][1]. Row 1 becomes [0,0,0] and column 1 becomes [0,0,0]. Other positions remain unchanged.
Constraints
- m == matrix.length
- n == matrix[0].length
- 1 ≤ m, n ≤ 200
- -2^31 ≤ matrix[i][j] ≤ 2^31 - 1
Editorial
Brute Force
Intuition
The most natural first thought is: scan the matrix, find every 0, and immediately set its entire row and column to 0. But there is a critical trap here — if you start setting cells to 0 during the scan, you cannot tell whether a 0 you encounter later was an original 0 or one that you just created. This leads to cascading zeroes that corrupt the entire matrix.
To avoid this problem, the simplest safe approach is to make a complete copy of the original matrix. Scan the copy to find where the original 0s are, then modify the original matrix based on what you found in the copy. This way, the reference data is never corrupted.
Think of it like taking a photograph of a whiteboard before erasing parts of it. You can always look at the photo to know what was originally written, even after you start erasing.
Step-by-Step Explanation
Let's trace through with matrix = [[1,1,1],[1,0,1],[1,1,1]]:
Step 1: Make a copy of the entire matrix.
- copy = [[1,1,1],[1,0,1],[1,1,1]]
Step 2: Scan the copy for 0s.
- [0][0]=1, [0][1]=1, [0][2]=1 — no zeros in row 0
- [1][0]=1, [1][1]=0 — FOUND a zero at [1][1]! Record row 1 and column 1.
- [1][2]=1, [2][0]=1, [2][1]=1, [2][2]=1 — no more zeros.
Step 3: For the zero found at [1][1], set entire row 1 to 0 in the original matrix.
- matrix[1] = [0, 0, 0]
Step 4: Set entire column 1 to 0 in the original matrix.
- matrix[0][1] = 0, matrix[1][1] = 0 (already 0), matrix[2][1] = 0
Step 5: Final result: [[1,0,1],[0,0,0],[1,0,1]]
Algorithm
- Create a deep copy of the matrix
- Scan the copy to find all positions containing 0
- For each 0 found at position [i][j] in the copy:
- Set every cell in row i of the original matrix to 0
- Set every cell in column j of the original matrix to 0
- The original matrix is now correctly modified in place
Code
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
// Make a copy of the matrix
vector<vector<int>> copy = matrix;
// Scan the copy for zeros
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (copy[i][j] == 0) {
// Zero out entire row i
for (int k = 0; k < n; k++)
matrix[i][k] = 0;
// Zero out entire column j
for (int k = 0; k < m; k++)
matrix[k][j] = 0;
}
}
}
}
};class Solution:
def setZeroes(self, matrix: list[list[int]]) -> None:
m, n = len(matrix), len(matrix[0])
# Make a deep copy of the matrix
copy = [row[:] for row in matrix]
# Scan the copy for zeros
for i in range(m):
for j in range(n):
if copy[i][j] == 0:
# Zero out entire row i
for k in range(n):
matrix[i][k] = 0
# Zero out entire column j
for k in range(m):
matrix[k][j] = 0class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
// Make a copy of the matrix
int[][] copy = new int[m][n];
for (int i = 0; i < m; i++)
copy[i] = matrix[i].clone();
// Scan the copy for zeros
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (copy[i][j] == 0) {
// Zero out entire row i
for (int k = 0; k < n; k++)
matrix[i][k] = 0;
// Zero out entire column j
for (int k = 0; k < m; k++)
matrix[k][j] = 0;
}
}
}
}
}Complexity Analysis
Time Complexity: O(m × n × (m + n))
We scan every cell of the m×n matrix. For each cell that is 0, we zero out its row (n operations) and its column (m operations). In the worst case, every cell is 0, giving us m×n cells each requiring (m+n) work = O(m × n × (m + n)).
Space Complexity: O(m × n)
We create a complete copy of the matrix which requires m × n extra space. This is the most wasteful part of this approach and motivates the next improvement.
Why This Approach Is Not Efficient
The brute force approach uses O(m × n) extra space to store the entire matrix copy. With m and n up to 200, this means up to 40,000 extra integers stored. While this is manageable for this problem's constraints, it is clearly wasteful.
The key insight is that we do not need to remember every cell — we only need to know which rows and which columns contain at least one zero. Once we know that, we can decide the fate of any cell [i][j] just by checking whether row i or column j was marked. This reduces the auxiliary storage from a full m×n matrix to just two arrays: one of size m (for rows) and one of size n (for columns).
Better Approach - Marker Arrays
Intuition
Instead of copying the entire matrix, we observe that the only information we really need is: "does row i contain a zero?" and "does column j contain a zero?" We can capture this with just two boolean arrays.
Think of it like a roll call. Instead of photocopying the entire attendance sheet, you just write down two lists: one for absent rows and one for absent columns. These two small lists contain all the information needed to reconstruct which cells should be zeroed.
The algorithm works in two passes:
- Detection pass: Scan every cell. When a 0 is found at [i][j], mark row[i] = true and col[j] = true.
- Modification pass: Scan every cell again. If row[i] or col[j] is marked, set matrix[i][j] = 0.
This clean separation of detection and modification prevents the cascading-zeros problem while using only O(m + n) extra space.
Step-by-Step Explanation
Let's trace through with matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]:
Step 1: Initialize marker arrays.
- row = [false, false, false]
- col = [false, false, false, false]
Step 2 (Detection pass): Scan matrix for zeros.
- [0][0]=0 → mark row[0]=true, col[0]=true
- [0][1]=1 → skip
- [0][2]=2 → skip
- [0][3]=0 → mark row[0]=true (already marked), col[3]=true
- [1][0]=3, [1][1]=4, [1][2]=5, [1][3]=2 → no zeros in row 1
- [2][0]=1, [2][1]=3, [2][2]=1, [2][3]=5 → no zeros in row 2
Step 3: Markers after detection: row = [true, false, false], col = [true, false, false, true]
Step 4 (Modification pass): Set cells to 0 based on markers.
- Row 0: row[0]=true → set ALL of row 0 to 0: [0,0,0,0]
- Row 1: row[1]=false → check columns: col[0]=true → [1][0]=0; col[3]=true → [1][3]=0. Others stay.
- Row 2: row[2]=false → check columns: col[0]=true → [2][0]=0; col[3]=true → [2][3]=0. Others stay.
Step 5: Result: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Marker Arrays — Detection Then Modification — Watch how we first scan the entire matrix to record which rows and columns contain zeros, then apply zeros in a second pass without corrupting any original data.
Algorithm
- Create two boolean arrays: row of size m and col of size n, both initialized to false
- Detection pass: For each cell [i][j] in the matrix:
- If matrix[i][j] == 0, set row[i] = true and col[j] = true
- Modification pass: For each cell [i][j] in the matrix:
- If row[i] is true OR col[j] is true, set matrix[i][j] = 0
- The matrix is now correctly modified in place
Code
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<bool> row(m, false), col(n, false);
// Detection pass: find all rows and columns with zeros
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;
}
}
}
// Modification pass: zero out marked rows and columns
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}
};class Solution:
def setZeroes(self, matrix: list[list[int]]) -> None:
m, n = len(matrix), len(matrix[0])
row = [False] * m
col = [False] * n
# Detection pass: find all rows and columns with zeros
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
row[i] = True
col[j] = True
# Modification pass: zero out marked rows and columns
for i in range(m):
for j in range(n):
if row[i] or col[j]:
matrix[i][j] = 0class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean[] row = new boolean[m];
boolean[] col = new boolean[n];
// Detection pass: find all rows and columns with zeros
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;
}
}
}
// Modification pass: zero out marked rows and columns
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}
}Complexity Analysis
Time Complexity: O(m × n)
We traverse the matrix exactly twice: once during the detection pass to find all zeros, and once during the modification pass to apply the zeroing. Each pass visits all m × n cells, performing O(1) work per cell. Total: 2 × m × n = O(m × n).
Space Complexity: O(m + n)
We use two auxiliary boolean arrays: one of size m for rows and one of size n for columns. This is a significant improvement over the O(m × n) space used by the brute force copy approach.
Why This Approach Is Not Efficient
The marker array approach is already very efficient in terms of time (O(m × n)), but it still uses O(m + n) extra space for the two marker arrays. The follow-up challenge asks: can we solve this with O(1) constant extra space?
The insight is that we are storing boolean flags for each row and each column — but the matrix itself already has a first row and a first column that we could repurpose as marker storage. Instead of allocating separate arrays, we can use the first row of the matrix to mark which columns need zeroing, and the first column to mark which rows need zeroing. The only complication is that the first row and first column themselves might contain original zeros, so we need two extra boolean variables to handle that edge case.
This eliminates the O(m + n) auxiliary space entirely, bringing us down to O(1) extra space.
Optimal Approach - In-Place Markers (Constant Space)
Intuition
The marker array approach used separate boolean arrays to track which rows and columns need zeroing. But notice: the matrix already has row 0 and column 0 sitting there — can we use those cells as our markers?
Yes! The idea is elegant: use matrix[i][0] (the first column) to indicate whether row i should be zeroed, and matrix[0][j] (the first row) to indicate whether column j should be zeroed. But there is a subtle overlap: cell matrix[0][0] belongs to both the first row and the first column, so it cannot serve double duty. We solve this by using matrix[0][0] for the first row marker only, and a separate boolean variable for the first column.
The algorithm works in phases:
- First, check if the first row and first column originally contain any zeros (store in two booleans).
- Use the rest of the matrix (rows 1..m-1, cols 1..n-1) to mark zeros into row 0 and column 0.
- Apply the markers to zero out the inner portion of the matrix.
- Finally, handle the first row and first column using the saved booleans.
The order matters: we must process the inner cells before touching row 0 and column 0, because those are still serving as markers.
Step-by-Step Explanation
Let's trace through with matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]:
Step 1: Check if first row has any zeros.
- Row 0 = [0,1,2,0] → YES, contains zeros. Set firstRowZero = true.
Step 2: Check if first column has any zeros.
- Column 0 = [0,3,1] → YES, contains a zero. Set firstColZero = true.
Step 3: Scan the inner matrix (rows 1..2, cols 1..3) for zeros. When found, mark the corresponding first-row and first-column cells.
- [1][1]=4, [1][2]=5, [1][3]=2 → no zeros
- [2][1]=3, [2][2]=1, [2][3]=5 → no zeros
- No inner zeros found, so row 0 and column 0 markers remain as they were.
Step 4: Apply markers to zero the inner matrix.
- For each cell [i][j] where i≥1 and j≥1: if matrix[i][0]==0 or matrix[0][j]==0, set matrix[i][j]=0.
- matrix[0][0]=0, so matrix[i][0] for all i checks against col 0 marker. matrix[1][0]=3≠0, matrix[2][0]=1≠0.
- matrix[0][1]=1, matrix[0][2]=2, matrix[0][3]=0.
- matrix[0][3]=0 → for all rows i: matrix[i][3]=0. So matrix[1][3]=0, matrix[2][3]=0.
- Inner matrix after: [[,1,2,],[3,4,5,0],[1,3,1,0]] (only col 3 affected).
Step 5: Handle first row: firstRowZero=true → set entire row 0 to zeros.
- Row 0 = [0,0,0,0]
Step 6: Handle first column: firstColZero=true → set entire column 0 to zeros.
- matrix[0][0]=0, matrix[1][0]=0, matrix[2][0]=0
Step 7: Final result: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
In-Place Markers — Constant Space Solution — Watch how the first row and first column of the matrix are repurposed as marker arrays, eliminating the need for any extra storage.
Algorithm
- Check if the first row contains any zero → store in boolean firstRowZero
- Check if the first column contains any zero → store in boolean firstColZero
- Scan the inner matrix (rows 1..m-1, cols 1..n-1). For each zero at [i][j], mark matrix[i][0] = 0 and matrix[0][j] = 0
- Apply markers to the inner matrix: for each cell [i][j] (i≥1, j≥1), if matrix[i][0] == 0 or matrix[0][j] == 0, set matrix[i][j] = 0
- If firstRowZero is true, set all cells in row 0 to 0
- If firstColZero is true, set all cells in column 0 to 0
Code
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool firstRowZero = false, firstColZero = false;
// Check if first row has any zero
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRowZero = true;
break;
}
}
// Check if first column has any zero
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstColZero = true;
break;
}
}
// Use first row and column as markers for inner matrix
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;
}
}
}
// Apply markers to inner matrix
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;
}
}
}
// Handle first row
if (firstRowZero) {
for (int j = 0; j < n; j++)
matrix[0][j] = 0;
}
// Handle first column
if (firstColZero) {
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])
# Check if first row has any zero
first_row_zero = any(matrix[0][j] == 0 for j in range(n))
# Check if first column has any zero
first_col_zero = any(matrix[i][0] == 0 for i in range(m))
# Use first row and column as markers for inner matrix
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# Apply markers to inner matrix
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
# Handle first row
if first_row_zero:
for j in range(n):
matrix[0][j] = 0
# Handle first column
if first_col_zero:
for i in range(m):
matrix[i][0] = 0class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean firstRowZero = false, firstColZero = false;
// Check if first row has any zero
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRowZero = true;
break;
}
}
// Check if first column has any zero
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstColZero = true;
break;
}
}
// Use first row and column as markers for inner matrix
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;
}
}
}
// Apply markers to inner matrix
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;
}
}
}
// Handle first row
if (firstRowZero) {
for (int j = 0; j < n; j++)
matrix[0][j] = 0;
}
// Handle first column
if (firstColZero) {
for (int i = 0; i < m; i++)
matrix[i][0] = 0;
}
}
}Complexity Analysis
Time Complexity: O(m × n)
We traverse the matrix a constant number of times: once to check the first row (O(n)), once to check the first column (O(m)), once to mark inner zeros (O(m × n)), once to apply markers (O(m × n)), and up to two more passes for the first row and column (O(n) + O(m)). Total: O(m × n), the same as the marker array approach.
Space Complexity: O(1)
We use only two boolean variables (firstRowZero and firstColZero) as extra storage. All marker information is stored within the matrix's own first row and first column. This is the optimal space complexity — you cannot solve this problem without at least reading every cell, and we store no extra information proportional to the input size.