LeetCode 73: Set Matrix Zeroes (In-Place Marker Strategy)
LeetCode 73MatrixIn-PlaceToday we solve LeetCode 73 - Set Matrix Zeroes.
Source: https://leetcode.com/problems/set-matrix-zeroes/
English
Problem Summary
Given an m x n integer matrix, if an element is 0, set its entire row and column to 0. You must do it in place.
Key Insight
Use the first row and first column as marker storage: when matrix[i][j] == 0, mark matrix[i][0] = 0 and matrix[0][j] = 0. Then zero cells based on these markers. Because first row/column are reused, track whether they originally contained zero with two flags.
Brute Force and Why Insufficient
Brute force collects all zero positions and then clears related rows/columns using extra sets or arrays. It works in O(mn) time but needs O(m+n) extra space. The follow-up asks for constant extra space.
Optimal Algorithm (Step-by-Step)
1) Scan first row to see if it should be zeroed (firstRowZero).
2) Scan first column to see if it should be zeroed (firstColZero).
3) For each cell (i,j) where i>0, j>0, if it is zero, mark its row/column in first column/row.
4) Second pass for i>0, j>0: set matrix[i][j] = 0 if its row marker or column marker is zero.
5) If firstRowZero is true, zero the whole first row; if firstColZero is true, zero the whole first column.
Complexity Analysis
Time: O(mn).
Space: O(1) extra space.
Common Pitfalls
- Forgetting to save first-row/first-column status before using them as markers.
- Clearing first row/column too early and destroying marker information.
- Starting marker passes from index 0 instead of 1.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean firstRowZero = false, firstColZero = false;
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRowZero = true;
break;
}
}
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstColZero = true;
break;
}
}
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 (firstRowZero) {
for (int j = 0; j < n; j++) matrix[0][j] = 0;
}
if (firstColZero) {
for (int i = 0; i < m; i++) matrix[i][0] = 0;
}
}
}func setZeroes(matrix [][]int) {
m, n := len(matrix), len(matrix[0])
firstRowZero, firstColZero := false, false
for j := 0; j < n; j++ {
if matrix[0][j] == 0 {
firstRowZero = true
break
}
}
for i := 0; i < m; i++ {
if matrix[i][0] == 0 {
firstColZero = true
break
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if matrix[i][j] == 0 {
matrix[i][0] = 0
matrix[0][j] = 0
}
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if matrix[i][0] == 0 || matrix[0][j] == 0 {
matrix[i][j] = 0
}
}
}
if firstRowZero {
for j := 0; j < n; j++ {
matrix[0][j] = 0
}
}
if firstColZero {
for i := 0; i < m; i++ {
matrix[i][0] = 0
}
}
}class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool firstRowZero = false, firstColZero = false;
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRowZero = true;
break;
}
}
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstColZero = true;
break;
}
}
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 (firstRowZero) {
for (int j = 0; j < n; j++) matrix[0][j] = 0;
}
if (firstColZero) {
for (int i = 0; i < m; i++) matrix[i][0] = 0;
}
}
};class Solution:
def setZeroes(self, matrix: list[list[int]]) -> None:
m, n = len(matrix), len(matrix[0])
first_row_zero = any(matrix[0][j] == 0 for j in range(n))
first_col_zero = 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_zero:
for j in range(n):
matrix[0][j] = 0
if first_col_zero:
for i in range(m):
matrix[i][0] = 0var setZeroes = function(matrix) {
const m = matrix.length, n = matrix[0].length;
let firstRowZero = false, firstColZero = false;
for (let j = 0; j < n; j++) {
if (matrix[0][j] === 0) {
firstRowZero = true;
break;
}
}
for (let i = 0; i < m; i++) {
if (matrix[i][0] === 0) {
firstColZero = true;
break;
}
}
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 (firstRowZero) {
for (let j = 0; j < n; j++) matrix[0][j] = 0;
}
if (firstColZero) {
for (let i = 0; i < m; i++) matrix[i][0] = 0;
}
};中文
题目概述
给定一个 m x n 矩阵，如果某个元素为 0，则将它所在的整行和整列都设为 0，并且要求原地修改。
核心思路
把第一行和第一列当作“标记位存储区”：若 matrix[i][j] == 0，就把 matrix[i][0] 与 matrix[0][j] 置零。之后根据标记批量清零。因为第一行和第一列本身也可能需要清零，必须提前用两个布尔变量记录它们初始是否含零。
朴素解法与不足
朴素方案是先记录所有零元素的位置，再用额外数组/集合标记要清零的行列，最后回填。时间复杂度同样是 O(mn)，但额外空间为 O(m+n)，不满足进阶要求。
最优算法（步骤）
1）先扫描第一行，记录 firstRowZero。
2）再扫描第一列，记录 firstColZero。
3）遍历内部区域（i>0, j>0），遇到 0 就在第一行/第一列打标记。
4）第二次遍历内部区域，若行标记或列标记为 0，则将当前格置 0。
5）最后根据两个布尔变量决定是否整体清零第一行与第一列。
复杂度分析
时间复杂度：O(mn)。
空间复杂度：O(1) 额外空间。
常见陷阱
- 忘记在打标记前保存第一行/第一列原始状态。
- 过早清零第一行或第一列，导致标记信息被破坏。
- 内部遍历从 0 开始，误改标记区。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean firstRowZero = false, firstColZero = false;
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRowZero = true;
break;
}
}
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstColZero = true;
break;
}
}
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 (firstRowZero) {
for (int j = 0; j < n; j++) matrix[0][j] = 0;
}
if (firstColZero) {
for (int i = 0; i < m; i++) matrix[i][0] = 0;
}
}
}func setZeroes(matrix [][]int) {
m, n := len(matrix), len(matrix[0])
firstRowZero, firstColZero := false, false
for j := 0; j < n; j++ {
if matrix[0][j] == 0 {
firstRowZero = true
break
}
}
for i := 0; i < m; i++ {
if matrix[i][0] == 0 {
firstColZero = true
break
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if matrix[i][j] == 0 {
matrix[i][0] = 0
matrix[0][j] = 0
}
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if matrix[i][0] == 0 || matrix[0][j] == 0 {
matrix[i][j] = 0
}
}
}
if firstRowZero {
for j := 0; j < n; j++ {
matrix[0][j] = 0
}
}
if firstColZero {
for i := 0; i < m; i++ {
matrix[i][0] = 0
}
}
}class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool firstRowZero = false, firstColZero = false;
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRowZero = true;
break;
}
}
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstColZero = true;
break;
}
}
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 (firstRowZero) {
for (int j = 0; j < n; j++) matrix[0][j] = 0;
}
if (firstColZero) {
for (int i = 0; i < m; i++) matrix[i][0] = 0;
}
}
};class Solution:
def setZeroes(self, matrix: list[list[int]]) -> None:
m, n = len(matrix), len(matrix[0])
first_row_zero = any(matrix[0][j] == 0 for j in range(n))
first_col_zero = 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_zero:
for j in range(n):
matrix[0][j] = 0
if first_col_zero:
for i in range(m):
matrix[i][0] = 0var setZeroes = function(matrix) {
const m = matrix.length, n = matrix[0].length;
let firstRowZero = false, firstColZero = false;
for (let j = 0; j < n; j++) {
if (matrix[0][j] === 0) {
firstRowZero = true;
break;
}
}
for (let i = 0; i < m; i++) {
if (matrix[i][0] === 0) {
firstColZero = true;
break;
}
}
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 (firstRowZero) {
for (let j = 0; j < n; j++) matrix[0][j] = 0;
}
if (firstColZero) {
for (let i = 0; i < m; i++) matrix[i][0] = 0;
}
};
Comments