Set Matrix Zeroes
Problem Statement
Given an m x n integer matrix, if an element is 0, set its entire row and column to 0. You must modify the matrix in place.
Input
A two-dimensional integer matrix matrix with m rows and n columns.
Output
No value is returned. The same matrix object is mutated so every row and column containing an original zero becomes all zeroes.
Constraints
- •
1 <= m, n <= 200 - •
-2^31 <= matrix[i][j] <= 2^31 - 1 - •
The matrix must be modified in place
Examples
Example 1
matrix = [[1,1,1],[1,0,1],[1,1,1]]
[[1,0,1],[0,0,0],[1,0,1]]Example 2
matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
[[0,0,0,0],[0,4,5,0],[0,3,1,0]]Learning Objectives
- Avoid corrupting future decisions by separating marking from zeroing.
- Use the first row and first column as marker storage for the rest of the matrix.
- Preserve whether the first row and first column themselves need zeroing with two flags.
- Apply markers in an order that does not destroy information too early.
Intuition
Pattern Recognition
The tempting direct approach zeroes a row and column as soon as a zero is seen. That destroys information because newly written zeroes look like original zeroes and can cascade incorrectly. A safer O(m + n) approach stores row and column marker arrays, but the premium in-place trick stores those markers inside the matrix itself.
Use the first cell of each row and each column as marker storage. The complication is that the first row and first column are both data and markers, so two boolean flags remember whether they originally contained a zero. After marking the inner matrix, zero the inner cells from the markers, then handle the first row and first column using the flags.
Common mistakes
- ×Zeroing rows and columns immediately during the discovery pass.
- ×Using the first row and first column as markers without separate flags for their original zero status.
- ×Zeroing the first row before using it to mark inner columns.
- ×Treating a zero created during the zeroing phase as if it were an original zero.
Algorithm Explanation
Key idea
Use matrix[row][0] to mark that row row must be zeroed, and matrix[0][col] to mark that column col must be zeroed. Two flags record whether row 0 or column 0 originally contained a zero.
Walkthrough
For matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]], the first row has zeroes, so firstRowZero = true. The first column has a zero at the top-left cell, so firstColZero = true. Scanning the inner cells finds no additional zeroes, but the first row markers already show columns 0 and 3 must be zeroed. Applying markers zeroes column 3 in the lower rows and keeps column 0 pending for the final flag step. Finally, firstRowZero zeroes the top row and firstColZero zeroes the left column.
Algorithm
- Scan the first row and set firstRowZero if any value is 0.
- Scan the first column and set firstColZero if any value is 0.
- For every inner cell, if it is 0, mark its row in matrix[row][0] and its column in matrix[0][col].
- Scan inner cells again. If the row marker or column marker is 0, set that cell to 0.
- If firstRowZero is true, zero the entire first row.
- If firstColZero is true, zero the entire first column.
Solutions
Solution: First row and column as markers
The matrix stores its own row and column markers. The first row and first column are reserved as marker arrays after two flags capture whether those marker areas must also be zeroed at the end.
Step-by-step
- Check row 0 and column 0 before writing any markers.
- Use inner zeroes to mark their row and column by writing zero into the first cell of that row and column.
- Zero the inner matrix based on those markers.
- Zero row 0 if its flag was set.
- Zero column 0 if its flag was set.
O(mn)
O(1)
The matrix is scanned a constant number of times and only two boolean flags are stored.
Java implementation
Dry Run
Sample input
matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]. Track the marker flags and marker row or column before applying zeroes.
| phase | inspection or update | firstRowZero | firstColZero | matrix or markers |
|---|---|---|---|---|
| check row 0 | row 0 contains zeroes at columns 0 and 3 | true | unknown | [[0,1,2,0],[3,4,5,2],[1,3,1,5]] |
| check column 0 | column 0 contains a zero at row 0 | true | true | [[0,1,2,0],[3,4,5,2],[1,3,1,5]] |
| mark inner cells | no inner zeroes are found | true | true | markers show column 0 and column 3 |
| zero inner cells | column marker at 3 zeroes lower rows in column 3 | true | true | [[0,1,2,0],[3,4,5,0],[1,3,1,0]] |
| apply first row flag | zero the entire first row | true | true | [[0,0,0,0],[3,4,5,0],[1,3,1,0]] |
| apply first column flag | zero the entire first column | true | true | [[0,0,0,0],[0,4,5,0],[0,3,1,0]] |
The final matrix matches the original zero locations, not the zeroes created during processing.
Interview Tips
Make the danger explicit: immediate zeroing creates false zeroes. Then present the first row and first column as reusable marker arrays. Be disciplined about order: capture first-row and first-column flags first, mark inner cells second, zero inner cells third, and only then zero the first row or first column.
Likely follow-ups
- How would you solve it with O(m + n) extra space, and why is that simpler?
- How would the algorithm change if the matrix were stored in a read-only format?
- How would you adapt this for a sparse matrix representation?
- What if each zero should affect only its diagonal instead of its row and column?
Similar Problems
Key Takeaways
- Do not zero immediately; mark first, then apply zeroes.
- The first row and first column can act as marker arrays.
- Two flags are required because the marker row and marker column are also real data.
- Apply first-row and first-column zeroing last to preserve marker information.