1. Problem Statement (Simple Explanation)
You’re given an m x n integer matrix.
Rule:
If any element matrix[i][j] is 0, then its entire row i and column j must be set to 0.
You must modify the matrix in-place.
2. Examples
Example 1:
Input:
matrix = [
[1,1,1],
[1,0,1],
[1,1,1]
]
matrix[1][1] == 0 → set row 1 and column 1 to zeros.
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
Example 2:
Input:
matrix = [
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Zero positions: (0,0) and (0,3).
Rows to zero: row 0
Cols to zero: col 0, col 3
Zeroing them yields:
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
3. Approaches
3.1 Naive (extra matrix, O(m·n) extra space):
Copy matrix, then for each zero in original, update row+col in copy. Not allowed (we want constant extra space).
3.2 Better (use O(m + n) extra space):
Use two arrays:
rows[m], cols[n] to mark which rows/cols contain zeros.
Second pass: zero out those rows and columns.
Still not optimal per follow-up: we want O(1) extra space.
4. Optimal O(1) Space Approach – Use First Row & First Column as Markers
Idea:
Use the first row and first column inside the matrix itself to record which rows and columns should be zeroed.
We also need two booleans:
firstRowZero – whether the first row itself must be zero.
firstColZero – whether the first column itself must be zero.
Steps:
Scan first row: if any matrix[0][j] == 0, set firstRowZero = true.
Scan first column: if any matrix[i][0] == 0, set firstColZero = true.
Use first row and column as markers:
For each cell (i, j) with i > 0 and j > 0:
If matrix[i][j] == 0:
Set matrix[i][0] = 0 (mark this row).
Set matrix[0][j] = 0 (mark this column).
Zero out cells based on markers:
For each cell (i, j) with i > 0, j > 0:
If matrix[i][0] == 0 or matrix[0][j] == 0:
Set matrix[i][j] = 0.
Zero out first row if needed:
If firstRowZero, set entire matrix[0][j] = 0 for all j.
Zero out first column if needed:
If firstColZero, set entire matrix[i][0] = 0 for all i.
This way:
We only use two booleans besides the matrix.
The matrix stores row/col markers in its first row and column.
Pseudo-code:
Time: O(m⋅n) – two passes over matrix.
Extra space: O(1) – only two booleans.
5. Java code
8. Python code
9. JavaScript code
Comments
Post a Comment