73: Set Matrix Zeroes
Problem Statement
Given an m x n integer matrix, set entire row and column to zeros if an element is 0. Must be done in-place.
Example 1
Input: [[1,1,1],[1,0,1],[1,1,1]] → Output: [[1,0,1],[0,0,0],[1,0,1]]Example 2
Input: [[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]]
Problem Link:
View on LeetCode ↗
Approach 1: Brute Force (O(mn) Space)
Use additional matrix to track zero positions, then update original matrix.
Algorithm Steps
- Create copy of original matrix
- Mark zeros in copy based on original matrix
- Update original matrix using copy
Brute Force Approach
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<vector<bool>> copy(m, vector<bool>(n, false));
// Mark zeros in copy
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(matrix[i][j] == 0) {
for(int k = 0; k < n; k++) copy[i][k] = true;
for(int k = 0; k < m; k++) copy[k][j] = true;
}
}
}
// Apply zeros
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(copy[i][j]) matrix[i][j] = 0;
}
}
}
};class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean[][] copy = new boolean[m][n];
// Mark zeros in copy
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(matrix[i][j] == 0) {
Arrays.fill(copy[i], true);
for(int k = 0; k < m; k++) copy[k][j] = true;
}
}
}
// Apply zeros
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(copy[i][j]) matrix[i][j] = 0;
}
}
}
}class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
copy = [[False] * n for _ in range(m)]
# Mark zeros
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
for k in range(n): copy[i][k] = True
for k in range(m): copy[k][j] = True
# Apply zeros
for i in range(m):
for j in range(n):
if copy[i][j]:
matrix[i][j] = 0
Drawback: Uses O(mn) space which is prohibited by problem constraints for optimal
solutions.
Approach 2: Linear Space (O(m + n))
Use separate arrays to track rows and columns containing zeros.
Linear Space Solution
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);
// Mark rows and columns
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;
}
}
}
// Set zeros
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(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean[] rows = new boolean[m];
boolean[] cols = new boolean[n];
// Mark rows and columns
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;
}
}
}
// Set zeros
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 = [False] * m
cols = [False] * n
# Mark rows and columns
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
rows[i] = True
cols[j] = True
# Apply zeros
for i in range(m):
for j in range(n):
if rows[i] or cols[j]:
matrix[i][j] = 0
Limitation: Still uses O(m + n) space which doesn't meet follow-up requirements.
Approach 3: Optimal In-Place (O(1) Space)
Use first row and column as markers, with special handling for first row/column.
Constant Space Solution
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool firstRow = false;
// Markers
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(matrix[i][j] == 0) {
matrix[0][j] = 0;
if(i == 0) firstRow = true;
else matrix[i][0] = 0;
}
}
}
// Process 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 column
if(matrix[0][0] == 0) {
for(int i = 0; i < m; i++) matrix[i][0] = 0;
}
// Handle first row
if(firstRow) {
for(int j = 0; j < n; j++) matrix[0][j] = 0;
}
}
};class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean firstRow = false;
// Markers
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(matrix[i][j] == 0) {
matrix[0][j] = 0;
if(i == 0) firstRow = true;
else matrix[i][0] = 0;
}
}
}
// Process 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 column
if(matrix[0][0] == 0) {
for(int i = 0; i < m; i++) matrix[i][0] = 0;
}
// Handle first row
if(firstRow) {
Arrays.fill(matrix[0], 0);
}
}
}class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
first_row = False
# Markers
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
matrix[0][j] = 0
if i == 0:
first_row = True
else:
matrix[i][0] = 0
# Process 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 column
if matrix[0][0] == 0:
for i in range(m):
matrix[i][0] = 0
# Handle first row
if first_row:
for j in range(n):
matrix[0][j] = 0
Optimization: Achieves O(1) space by reusing matrix's first row/column as markers.
Approach Comparison
| Approach | Time | Space | Readability | Optimal |
|---|---|---|---|---|
| Brute Force | O(mn(m + n)) | O(mn) | Simple | ❌ |
| Linear Space | O(mn) | O(m + n) | Good | ❌ |
| Constant Space | O(mn) | O(1) | Complex | ✅ |
Important: Optimal approach requires careful handling of first row/column edge cases.
Edge Cases
1. Zero in First Row/Column
Input: [[0,1],[1,1]] → Output: [[0,0],[0,1]]2. Matrix with No Zeros
Input: [[1,2],[3,4]] → Output: [[1,2],[3,4]]3. All Elements Zero
Input: [[0,0],[0,0]] → Output: [[0,0],[0,0]]
Testing Tip: Always verify cases where first row/column contains zeros initially.
Frequently Asked Questions
Why not use O(mn) space approach?
For large matrices (200x200), it would require 40,000 storage units which is memory inefficient.
How does the optimal approach handle overlapping zeros?
Markers are set first before modification, preventing interference with subsequent zero detection.
Why separate handling for first row/column?
The first row/column serve as markers and need special treatment to avoid overwriting marker information.
Can we use boolean variables instead of markers?
Yes, but requires additional variables for first row/column state tracking as shown in the optimal approach.
What if a zero appears in marker row/column?
It's handled naturally through the marker system - zeros in markers will trigger corresponding row/column clears.
How to handle negative numbers?
Marker system works regardless of values since we only care about zero positions.
Why process inner matrix first?
To prevent marker row/column modification from affecting inner matrix processing.
Can this be extended to 3D matrices?
Yes, but would require more complex marker tracking across multiple dimensions.
What's the time complexity?
O(mn) for all approaches, as we need to scan entire matrix at least once.
How to verify in-place modification?
Check that matrix reference remains same, only element values change.
Why not use separate marker values?
Problem constraints allow any integer values, so special markers could conflict with existing values.
What if matrix is empty?
Constraints guarantee 1 <= m, n <=200, so empty matrix isn't possible.
Final Recommendation: The optimal in-place approach provides the best space efficiency
while maintaining O(mn) time complexity.