Set Matrix Zeros
Java coding interview problem for Matrix Problems: Set Matrix Zeros.
The Set Matrix Zeroes problem is one of the most popular matrix manipulation problems asked in coding interviews.
It tests your understanding of:
- Matrix traversal
- In-place modification
- Space optimization
- Row and column relationships
- Handling edge cases
This problem is commonly asked by:
- Amazon
- Microsoft
- Meta
- Apple
What is Set Matrix Zeroes?
Given a matrix, if an element contains:
0
then set its entire:
Row
and
Column
to zero.
The transformation must be done according to the original matrix values.
Example 1
Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
The zero exists at:
row = 1
column = 1
Set:
Row 1 → zero
Column 1 → zero
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]
]
Zeros exist at:
(0,0)
(0,3)
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
Understanding the Problem
Consider:
1 2 3
4 0 6
7 8 9
The zero is at:
[1][1]
Affected:
Row:
4 0 6
Column:
2
0
8
Final matrix:
1 0 3
0 0 0
7 0 9
Why Is Set Matrix Zeroes Asked in Interviews?
This problem tests:
1. Space Optimization
Can you reduce:
O(m × n)
extra memory?
to:
O(1)
?
2. In-place Modification
Can you modify the original matrix without creating another matrix?
3. Edge Case Handling
Can you correctly handle:
- First row
- First column
- Multiple zeros
- Already zero values
4. Algorithm Design
Can you improve from:
Brute Force
↓
Optimized Solution
?
Real-World Applications
Image Processing
Images are matrices of pixels.
If a pixel condition is invalid:
0
entire rows or columns may need modification.
Data Cleaning
In data matrices:
Missing value = 0
may require clearing related records.
Spreadsheet Processing
Rows and columns may be marked invalid based on specific cell values.
Machine Learning
Feature matrices sometimes require masking invalid dimensions.
Problem Statement
Given an:
m × n matrix
if any cell contains:
0
set its entire row and column to zero.
Modify the matrix in-place.
Constraints
Example:
1 <= rows <= 200
1 <= columns <= 200
Values:
-2^31 <= matrix[i][j] <= 2^31-1
Important Observation
The challenge is:
If we directly change rows and columns while scanning, new zeros may affect future processing.
Example:
Input:
1 2 3
4 0 6
7 8 9
If we immediately update:
Row 1
and:
Column 1
while traversing, we may incorrectly process newly created zeros.
Therefore:
We need to remember:
Which rows contain zeros
Which columns contain zeros
before modifying.
Matrix Visualization
Input:
1 2 3 4
5 0 7 8
9 10 11 12
Find zeros:
Position:
[1][1]
Mark:
Row:
1
Column:
1
Result:
1 0 3 4
0 0 0 0
9 0 11 12
Approach 1 — Brute Force Approach
The simplest approach:
Whenever we find:
0
mark its complete row and column.
Algorithm
- Traverse matrix.
- Find zero elements.
- Store zero positions.
- Update corresponding rows and columns.
Why Store Positions?
Because modifying immediately can create false zeros.
Example:
Original:
1 2 3
4 0 6
7 8 9
After finding zero:
Store:
(1,1)
Then update later.
Java Program — Brute Force
import java.util.ArrayList;
import java.util.List;
public class SetMatrixZeroesBruteForce {
public static void setZeroes(
int[][] matrix) {
List<int[]> zeros =
new ArrayList<>();
int rows =
matrix.length;
int cols =
matrix[0].length;
// Store zero positions
for(int i = 0;
i < rows;
i++) {
for(int j = 0;
j < cols;
j++) {
if(matrix[i][j] == 0) {
zeros.add(
new int[]{i,j});
}
}
}
// Update rows and columns
for(int[] position : zeros) {
int row =
position[0];
int col =
position[1];
// Set row zero
for(int j = 0;
j < cols;
j++) {
matrix[row][j] = 0;
}
// Set column zero
for(int i = 0;
i < rows;
i++) {
matrix[i][col] = 0;
}
}
}
public static void main(String[] args) {
int[][] matrix =
{
{1,1,1},
{1,0,1},
{1,1,1}
};
setZeroes(matrix);
for(int[] row : matrix) {
for(int value : row) {
System.out.print(
value + " ");
}
System.out.println();
}
}
}
Output
1 0 1
0 0 0
1 0 1
Step-by-Step Explanation
Input:
1 1 1
1 0 1
1 1 1
Find zero:
matrix[1][1]
Store:
row = 1
column = 1
Set row:
1 0 1
becomes:
0 0 0
Set column:
column 1
becomes:
0
0
0
Final:
1 0 1
0 0 0
1 0 1
Complexity Analysis
Let:
m = rows
n = columns
Finding zeros:
O(m × n)
Updating rows and columns:
Worst case:
O(m × n)
Total:
Time Complexity: O(m × n)
Space:
Stores zero positions:
O(m × n)
Worst case.
Advantages
- Easy to understand.
- Simple implementation.
- Works correctly.
Drawbacks
- Uses extra memory.
- Not optimal for interviews.
- Stores unnecessary information.
Approach 2 — Row and Column Marker Arrays
Instead of storing every zero position, store:
Which rows need zero
Which columns need zero
Example:
Matrix:
1 2 3
4 0 6
7 8 9
Create:
Rows:
[false,true,false]
Columns:
[false,true,false]
Then update matrix.
Approach 2 — Row and Column Marker Arrays
The marker array approach improves the brute force solution by avoiding storage of every zero position.
Instead of storing:
(row, column)
positions, we maintain two arrays:
rows[]
columns[]
to remember which rows and columns should become zero.
Core Idea
For every zero element:
matrix[i][j] == 0
mark:
rows[i] = true
columns[j] = true
After scanning the complete matrix:
- Set marked rows to zero.
- Set marked columns to zero.
Example
Input:
1 2 3
4 0 6
7 8 9
Create row markers:
rows:
[false,false,false]
Column markers:
columns:
[false,false,false]
Find zero:
Position:
[1][1]
Mark:
rows[1] = true
columns[1] = true
Markers become:
Rows:
[false,true,false]
Columns:
[false,true,false]
Update matrix:
Final:
1 0 3
0 0 0
7 0 9
Java Program — Marker Arrays
public class SetMatrixZeroesMarker {
public static void setZeroes(
int[][] matrix) {
int rows =
matrix.length;
int cols =
matrix[0].length;
boolean[] rowMarker =
new boolean[rows];
boolean[] colMarker =
new boolean[cols];
// Find zero positions
for(int i = 0;
i < rows;
i++) {
for(int j = 0;
j < cols;
j++) {
if(matrix[i][j] == 0) {
rowMarker[i] = true;
colMarker[j] = true;
}
}
}
// Set rows to zero
for(int i = 0;
i < rows;
i++) {
if(rowMarker[i]) {
for(int j = 0;
j < cols;
j++) {
matrix[i][j] = 0;
}
}
}
// Set columns to zero
for(int j = 0;
j < cols;
j++) {
if(colMarker[j]) {
for(int i = 0;
i < rows;
i++) {
matrix[i][j] = 0;
}
}
}
}
public static void main(String[] args) {
int[][] matrix =
{
{1,2,3},
{4,0,6},
{7,8,9}
};
setZeroes(matrix);
for(int[] row : matrix) {
for(int value : row) {
System.out.print(
value + " ");
}
System.out.println();
}
}
}
Output
1 0 3
0 0 0
7 0 9
Complexity Analysis
For:
m × n matrix
Finding zeros:
O(m × n)
Updating matrix:
O(m × n)
Total:
Time Complexity: O(m × n)
Space:
Row marker:
O(m)
Column marker:
O(n)
Total:
O(m+n)
Advantages
- Cleaner than brute force.
- Avoids storing all zero locations.
- Easy to implement.
- Good interview solution.
Drawbacks
Requires extra memory:
O(m+n)
Approach 3 — Optimal Constant Space Approach
The interview-preferred solution uses:
First Row
and
First Column
as marker storage.
Core Idea
Instead of creating:
rows[]
columns[]
we reuse the matrix itself.
For every zero:
matrix[i][j] = 0
mark:
matrix[i][0] = 0
matrix[0][j] = 0
Example:
Input:
1 2 3
4 0 6
7 8 9
Zero found:
[1][1]
Mark:
First column:
matrix[1][0] = 0
First row:
matrix[0][1] = 0
Matrix becomes:
1 0 3
0 0 6
7 8 9
Then use markers to update remaining cells.
Important Edge Case
The first row and first column are special.
Example:
0 1 2
3 4 5
6 7 8
The first row contains zero.
If we use:
matrix[0][j]
as markers, we need to remember:
Should first row become zero?
Similarly:
Should first column become zero?
Therefore we store two flags:
firstRowZero
firstColumnZero
Algorithm
Step 1
Check whether first row contains zero.
Store:
firstRowZero
Step 2
Check whether first column contains zero.
Store:
firstColumnZero
Step 3
Use first row and first column as markers.
For every cell:
matrix[i][j] == 0
mark:
matrix[i][0] = 0
matrix[0][j] = 0
Step 4
Update inner matrix:
Ignore first row and first column.
Step 5
Update first row and first column using saved flags.
Java Program — Optimal O(1) Space
public class SetMatrixZeroesOptimal {
public static void setZeroes(
int[][] matrix) {
int rows =
matrix.length;
int cols =
matrix[0].length;
boolean firstRowZero = false;
boolean firstColumnZero = false;
// Check first row
for(int j = 0;
j < cols;
j++) {
if(matrix[0][j] == 0) {
firstRowZero = true;
break;
}
}
// Check first column
for(int i = 0;
i < rows;
i++) {
if(matrix[i][0] == 0) {
firstColumnZero = true;
break;
}
}
// Use first row and column as markers
for(int i = 1;
i < rows;
i++) {
for(int j = 1;
j < cols;
j++) {
if(matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// Set inner cells
for(int i = 1;
i < rows;
i++) {
for(int j = 1;
j < cols;
j++) {
if(matrix[i][0] == 0 ||
matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
// First row
if(firstRowZero) {
for(int j = 0;
j < cols;
j++) {
matrix[0][j] = 0;
}
}
// First column
if(firstColumnZero) {
for(int i = 0;
i < rows;
i++) {
matrix[i][0] = 0;
}
}
}
}
Dry Run
Input:
1 2 3
4 0 6
7 8 9
Initial:
firstRowZero = false
firstColumnZero = false
Find zero:
matrix[1][1]
Mark:
matrix[1][0] = 0
matrix[0][1] = 0
Matrix:
1 0 3
0 0 6
7 8 9
Process inner cells:
Cell:
[1][2]
Row marker:
matrix[1][0] = 0
Set:
[1][2] = 0
Final:
1 0 3
0 0 0
7 0 9
Complexity Analysis
Time:
O(m × n)
Space:
O(1)
Advantages
- Optimal solution.
- No extra arrays.
- Interview expected approach.
- In-place modification.
Drawbacks
- More complex.
- Requires careful first row/column handling.
Java Streams Approach
Streams are not recommended for this problem.
Reason:
The algorithm requires:
- In-place mutation.
- Marker management.
- Multiple traversal phases.
Traditional loops provide:
- Better readability.
- Better performance.
- Easier debugging.
Comparison of All Approaches
| Approach | Time | Space | Recommendation |
|---|---|---|---|
| Brute Force | O(m×n) | O(m×n) | Learning |
| Marker Arrays | O(m×n) | O(m+n) | Good |
| First Row/Column Markers | O(m×n) | O(1) | Best Interview Solution |
Matrix Index Mapping
A matrix element is accessed using:
matrix[row][column]
Example:
matrix[2][3]
means:
Row:
2
Column:
3
Primitive vs Object Arrays
Primitive Matrix
int[][]
Advantages:
- Faster.
- Less memory.
- Better performance.
Object Matrix
Integer[][]
Advantages:
- Supports null values.
- Works with collections.
Common Interview Mistakes
Mistake 1
Changing values while finding zeros.
Problem:
New zeros create incorrect updates.
Mistake 2
Forgetting first row and first column flags.
Mistake 3
Using first row markers before saving original state.
Mistake 4
Extra space when O(1) is expected.
Edge Cases
| Input | Result |
|---|---|
| Empty matrix | Handle separately |
| No zeros | No change |
| All zeros | All zero |
| Single element 0 | Zero |
| Zero in first row | Handled by flag |
| Zero in first column | Handled by flag |
Interview Follow-up Questions
Q1. Solve Set Matrix Zeroes in O(1) space.
Q2. Why cannot we update immediately?
Q3. Explain first row and column markers.
Q4. Modify only rows.
Q5. Modify only columns.
Q6. Find rows containing zeros.
Q7. Find columns containing zeros.
Related Problems
- Matrix Rotation
- Matrix Transpose
- Spiral Matrix
- Search in Matrix
- Rotate Image
- Game of Life
- Flood Fill
Key Takeaways
Set Matrix Zeroes teaches an important optimization pattern:
Extra Memory
↓
Marker Arrays
↓
Use Input Matrix as Storage
The optimal interview solution:
First Row + First Column Markers
Complexity:
Time: O(m × n)
Space: O(1)
Frequently Asked Interview Questions
Q1. Why use first row and first column?
To store marker information without extra memory.
Q2. Why need two boolean flags?
Because first row and first column are used as markers.
Their original zero state must be preserved.
Q3. What is the optimal complexity?
O(m × n) time
O(1) space
Q4. Can this be solved with extra space?
Yes, using row and column arrays.
Interview Tip
When asked:
"Set Matrix Zeroes."
Explain the optimization journey:
Brute Force
↓
Row/Column Arrays
↓
First Row + First Column Markers
For senior interviews, focus on:
- Why immediate updates fail.
- How marker storage works.
- How edge cases are handled.
This demonstrates strong understanding of in-place algorithms and matrix optimization.