Approach Summary
Use first row and column as markers. Mark zero locations, then zero out rows/columns accordingly.
Full Solution & Approach
The challenge is the O(1) space constraint. Instead of a separate row/column marker array, use the first row and first column as markers. First save their original state by checking whether row 0 and column 0 contain any zero. Then scan the matrix; for every cell that is zero, mark its row and column by writing 0 to matrix[i][0] and matrix[0][j]. Zero out the inner cells next: any cell whose row marker or column marker is 0 becomes 0. Finally, handle the first row and first column using the saved flags. The two-phase approach — mark, then apply — ensures markers are read before being overwritten, which is the classic trap in this problem.
Two passes over the matrix — O(m × n) time. Only two boolean flags plus the matrix itself — O(1) extra space.
Solution Code
Solution
def set_zeroes(matrix: list[list[int]]) -> None:
m, n = len(matrix), len(matrix[0])
first_row = any(matrix[0][j] == 0 for j in range(n))
first_col = any(matrix[i][0] == 0 for i in range(m))
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
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
if first_row:
for j in range(n):
matrix[0][j] = 0
if first_col:
for i in range(m):
matrix[i][0] = 0function setZeroes(matrix) {
const m = matrix.length, n = matrix[0].length;
const firstRow = matrix[0].some(v => v === 0);
const firstCol = matrix.some(row => row[0] === 0);
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][j] === 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][0] === 0 || matrix[0][j] === 0) matrix[i][j] = 0;
}
}
if (firstRow) for (let j = 0; j < n; j++) matrix[0][j] = 0;
if (firstCol) for (let i = 0; i < m; i++) matrix[i][0] = 0;
}public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean firstRow = false, firstCol = false;
for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRow = true;
for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstCol = true;
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; }
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;
if (firstRow) for (int j = 0; j < n; j++) matrix[0][j] = 0;
if (firstCol) for (int i = 0; i < m; i++) matrix[i][0] = 0;
}void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool firstRow = false, firstCol = false;
for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRow = true;
for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstCol = true;
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; }
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;
if (firstRow) for (int j = 0; j < n; j++) matrix[0][j] = 0;
if (firstCol) for (int i = 0; i < m; i++) matrix[i][0] = 0;
}Edge Cases to Watch
- A zero in the first row or column — the saved flags preserve them
- Single cell [0] — first_row and first_col are both true
- All zeros — the whole matrix is already zero
- No zeros — returned unchanged
How to Recognize This Pattern
- Zero out rows and columns in-place
- Use first row/col as flags
Complexity Analysis
Time Complexity
O(m × n)
Space Complexity
O(1)