73. Set Matrix Zeroes

題目 / Problem

中文： 給定一個 m x n 的整數矩陣 matrix。如果某個元素是 0，就把它所在的「整行」和「整列」全部設為 0。你必須原地（in place）完成，也就是直接在原矩陣上修改，盡量不要額外開一個一樣大的矩陣。

English: Given an m x n integer matrix matrix, if a cell equals 0, set its entire row and entire column to 0. You must do it in place — modify the given matrix directly, ideally without allocating another full-size matrix.

Constraints / 限制： - m == matrix.length, n == matrix[0].length - 1 <= m, n <= 200 - -2³¹ <= matrix[i][j] <= 2³¹ - 1 - Follow up: try to do it with O(1) extra space.

Worked example / 範例：

Input:  [[1,1,1],
         [1,0,1],
         [1,1,1]]
Output: [[1,0,1],
         [0,0,0],
         [1,0,1]]

中間那個 0 位在第 1 行、第 1 列（從 0 數起），所以整個第 1 行和整個第 1 列都變成 0。 The single 0 sits at row 1, column 1, so row 1 and column 1 both become all zeros.

名詞解釋 / Glossary

矩陣 / matrix： 二維的數字表格，用 matrix[i][j] 取第 i 行第 j 列的元素。In C it is often a int** (array of row pointers); in C++ a vector<vector<int>>.
原地修改 / in-place： 不另外配置一塊和輸入一樣大的記憶體，直接在原資料上改。目標是把額外空間降到很小。Modifying the input directly using only a tiny, fixed amount of extra memory.
空間複雜度 / space complexity： 演算法執行時「額外」用掉多少記憶體（不含輸入本身）。O(1) 表示固定、與輸入大小無關。How much extra memory an algorithm uses beyond the input.
標記 / marker (flag)： 借用矩陣裡某些既有格子來「記住」資訊，而不是另開陣列。Here we reuse the first row and first column as flags telling us which rows/columns must be zeroed.
遍歷 / traverse (iterate)： 用迴圈一格一格走過矩陣的所有元素。Looping over every cell once.

思路

中文： 最直覺的暴力法是：邊掃描邊把 0 所在的行列清零。但這會出問題——你剛清出來的 0 會被後面的掃描誤認成「原本就是 0」，於是把更多無辜的行列也清掉，結果整個矩陣都變 0。所以第一個關鍵是：先找出哪些行、哪些列要清零，全部找完之後再動手清。 一個簡單的做法是開兩個布林陣列 rows[m] 和 cols[n]，掃一遍把要清的行列記下來，再掃第二遍：只要 rows[i] 或 cols[j] 為真就把 matrix[i][j] 設 0。這用了 O(m+n) 額外空間，正確但不是最省。

要做到 O(1) 空間，重點是：那兩個布林陣列其實可以「藏」在矩陣自己身上。我們挑第一行當作 cols[]（記哪些列要清），挑第一列當作 rows[]（記哪些行要清）。但第一行和第一列彼此共用左上角 matrix[0][0] 這一格，會打架，所以另外用一個變數 firstColZero 單獨記「第一列本身需不需要清零」。流程是：先單獨判斷第一列是否含 0；接著掃描其餘格子，發現 matrix[i][j]==0 就把它的「行標記」matrix[i][0] 和「列標記」matrix[0][j] 設為 0；然後從第二行第二列開始，根據標記回填 0；最後再處理第一行（看 matrix[0][0]）和第一列（看 firstColZero）。之所以要從外往內、最後才處理第一行/列，是因為它們存著標記資訊，必須等所有內部格子讀完才能覆蓋掉。

English: The naive idea — zero out rows and columns the moment you see a 0 — is broken: the zeros you just wrote get mistaken for original zeros later in the scan, cascading until the whole matrix is wiped. So the first principle is decide everything first, then apply: do one pass to record which rows and columns need clearing, then a second pass to actually clear them. A clean version uses two boolean arrays rows[m] and cols[n]. That's correct and uses O(m+n) extra space, but we can do better.

For O(1) space, notice those two boolean arrays can be stored inside the matrix itself. Use the first row as the column-flags and the first column as the row-flags. The catch: both overlap at matrix[0][0], so they'd clash. We resolve it with one extra scalar firstColZero that separately remembers whether the first column needs zeroing. The steps: (1) check if the first column originally contains a 0; (2) scan the inner cells — whenever matrix[i][j]==0, mark matrix[i][0]=0 and matrix[0][j]=0; (3) for inner cells (from row 1, col 1), zero them out if either their row-flag or column-flag is set; (4) finally handle the first row using matrix[0][0] and the first column using firstColZero. We process the first row/column last precisely because they hold the flags — we mustn't overwrite them until every inner cell has read them.

逐步走查 / Walkthrough

輸入 / Input: [[1,1,1],[1,0,1],[1,1,1]]（m=3, n=3）

步驟 / Step	動作 / Action	矩陣狀態 / Matrix state
0. 初始 / start	設 `firstColZero=false`（第一列是 1,1,1，沒有 0）/ first column has no zero	`[[1,1,1],[1,0,1],[1,1,1]]`
1. 掃內部找 0 / scan inner cells	走訪 i=0..2, j=1..2。在 `i=1,j=1` 發現 0 → 設行標記 `matrix[1][0]=0`、列標記 `matrix[0][1]=0` / mark row 1 and col 1	`[[1,0,1],[0,0,1],[1,1,1]]`
2. 回填內部 / apply to inner	從 i=1, j=1 開始。`matrix[1][1]`：行標記`matrix[1][0]=0` → 設 0（已是 0）。`matrix[1][2]`：行標記為 0 → 設 0。`matrix[2][1]`：列標記`matrix[0][1]=0` → 設 0。`matrix[2][2]`：兩標記皆非 0 → 不動	`[[1,0,1],[0,0,0],[1,0,1]]`
3. 處理第一行 / first row	`matrix[0][0]=1`（不是 0）→ 第一行不清 / first row stays	`[[1,0,1],[0,0,0],[1,0,1]]`
4. 處理第一列 / first column	`firstColZero=false` → 第一列不清 / first column stays	`[[1,0,1],[0,0,0],[1,0,1]]`
✅ 結果 / result	與預期輸出相符 / matches expected	`[[1,0,1],[0,0,0],[1,0,1]]`

Solution — C

// 演算法 / Algorithm:
// 用第一行當「列要清零」的標記、第一列當「行要清零」的標記，
// 額外一個變數記第一列本身要不要清零，達到 O(1) 額外空間。
// Use first row as column-flags and first column as row-flags; one extra
// scalar tracks the first column itself. Result: O(1) extra space.

// matrixSize 是行數 m / matrixSize is the number of rows (m).
// matrixColSize[i] 是第 i 行的列數 / matrixColSize[i] is the column count of row i.
void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize;          // 行數 / number of rows
    int n = matrixColSize[0];    // 列數（每行一樣寬）/ number of columns (rows are uniform)

    // firstColZero 記第一列原本有沒有 0 / does the first column originally contain a 0?
    // 用 int 當布林：0=false, 1=true / use int as a boolean flag.
    int firstColZero = 0;

    // 第一步：單獨檢查第一列，因為它和第一行共用 matrix[0][0]，不能用同一格存兩件事。
    // Step 1: check the first column separately — it shares matrix[0][0] with the first row.
    for (int i = 0; i < m; i++) {        // 走過每一行的第 0 列 / scan column 0 of every row
        if (matrix[i][0] == 0) {         // 若該格是 0 / if this cell is zero
            firstColZero = 1;            // 記住整個第一列稍後要清 / remember to clear column 0 later
        }
    }

    // 第二步：掃描「除第一列外」的所有格子，把 0 的資訊記到第一行/第一列的標記上。
    // Step 2: scan all cells except column 0; record zeros into the flag row/column.
    for (int i = 0; i < m; i++) {            // 每一行 / each row
        for (int j = 1; j < n; j++) {        // 從 j=1 開始，跳過第一列 / start at j=1, skip column 0
            if (matrix[i][j] == 0) {         // 發現一個 0 / found a zero
                matrix[i][0] = 0;            // 行標記：此行要清 / row-flag: this row must be cleared
                matrix[0][j] = 0;            // 列標記：此列要清 / column-flag: this column must be cleared
            }
        }
    }

    // 第三步：根據標記回填內部格子（從第 1 行、第 1 列開始，避免覆蓋標記）。
    // Step 3: use the flags to zero inner cells (start at row 1, col 1 so flags stay intact).
    for (int i = 1; i < m; i++) {            // 從第 1 行開始 / from row 1
        for (int j = 1; j < n; j++) {        // 從第 1 列開始 / from column 1
            // 若此行被標記、或此列被標記，就把這格設 0。
            // If this row or this column was flagged, zero this cell.
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }

    // 第四步：最後才處理第一行。matrix[0][0] 同時代表「第一行要不要清」。
    // Step 4: handle the first row last. matrix[0][0] tells us if the first row needs clearing.
    if (matrix[0][0] == 0) {                 // 第一行需要清零 / first row must be zeroed
        for (int j = 0; j < n; j++) {        // 整個第一行設 0 / set entire first row to 0
            matrix[0][j] = 0;
        }
    }

    // 第五步：用先前存的 firstColZero 處理第一列。
    // Step 5: use the saved firstColZero to clear the first column if needed.
    if (firstColZero) {                      // 第一列需要清零 / first column must be zeroed
        for (int i = 0; i < m; i++) {        // 整個第一列設 0 / set entire column 0 to 0
            matrix[i][0] = 0;
        }
    }
}

Solution — C++

// 演算法 / Algorithm:
// 與 C 版相同：第一行存「列要清」的旗標、第一列存「行要清」的旗標，
// 另用一個 bool 記第一列本身，達成 O(1) 額外空間。
// Same as C: first row = column-flags, first column = row-flags, plus one
// bool for the first column itself → O(1) extra space.

class Solution {
public:
    // vector<vector<int>>& 是「二維向量的參考」/ a reference to a 2D vector.
    // 用 & 代表直接改原矩陣，不複製 / the & means we modify the original in place, no copy.
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();        // 行數 / number of rows (.size() gives element count)
        int n = matrix[0].size();     // 列數 / number of columns

        // 記第一列原本是否含 0 / does the first column originally contain a 0?
        bool firstColZero = false;

        // 第一步：單獨檢查第一列（它與第一行共用 matrix[0][0]）。
        // Step 1: check the first column separately (it shares matrix[0][0] with the first row).
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) firstColZero = true;  // 標記稍後要清第一列 / clear col 0 later
        }

        // 第二步：掃描第一列以外的格子，把 0 的資訊寫進標記行/列。
        // Step 2: scan all cells except column 0, recording zeros into the flag row/column.
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {       // j 從 1 開始跳過第一列 / start at 1 to skip column 0
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;           // 行標記 / row-flag
                    matrix[0][j] = 0;           // 列標記 / column-flag
                }
            }
        }

        // 第三步：依標記回填內部格子（從 1,1 開始，保留標記不被覆蓋）。
        // Step 3: apply flags to inner cells (start at 1,1 so flags aren't overwritten yet).
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 此行或此列被標記則設 0 / zero if this row or column was flagged.
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            }
        }

        // 第四步：最後處理第一行 / Step 4: handle the first row last.
        if (matrix[0][0] == 0) {
            for (int j = 0; j < n; j++) matrix[0][j] = 0;  // 整行設 0 / zero the whole first row
        }

        // 第五步：依 firstColZero 處理第一列 / Step 5: clear the first column if flagged.
        if (firstColZero) {
            for (int i = 0; i < m; i++) matrix[i][0] = 0;  // 整列設 0 / zero the whole first column
        }
    }
};

複雜度 / Complexity

Time: O(m·n) — 我們對矩陣做了固定次數的完整遍歷（找標記、回填等共數趟），每趟都是 m×n 個格子。總時間由格子總數決定，常數倍不影響大 O。We pass over the m×n cells a constant number of times; total work is proportional to the number of cells.
Space: O(1) — 只用了 firstColZero 等少數變數，所有「要清哪些行列」的資訊都存在矩陣自己的第一行/第一列裡，沒有隨輸入增大而增長的額外記憶體。Only a few scalar variables; the row/column flags are stored inside the matrix itself, so extra memory does not grow with input size.

Pitfalls & Edge Cases

邊掃邊清會連鎖崩壞 / Clearing while scanning cascades: 若一看到 0 就馬上清整行整列，新寫的 0 會被後面當成原始 0，導致越清越多。本解法分「先記標記、後回填」兩階段避免此問題。Always record first, apply later.
第一行與第一列的衝突 / First row vs. first column clash: 兩者共用 matrix[0][0]，無法用同一格同時記兩種旗標。所以額外用 firstColZero 變數獨立保存第一列。Don't try to encode both flags in matrix[0][0].
處理順序很重要 / Order matters: 必須最後才清第一行和第一列，因為它們存著標記；提早覆蓋會讓內部格子讀到錯誤資訊。Inner cells (loop from index 1) must be done before the first row/column.
不要用 0 當「臨時標記值」/ Don't pick 0 as a sentinel by accident: 用矩陣裡的 0 本身當旗標就好；若改用其他數字（如 -1）當標記，要小心輸入本來可能就含那個數字。Here we reuse the natural value 0, which is safe.
單行或單列矩陣 / Single row or column (m=1 or n=1): 迴圈用 < m、< n 邊界，且第一行/第一列的處理涵蓋這些退化情況，不會越界。The bounds handle 1×n and m×1 matrices correctly.
大數值不影響 / Large values are fine: 元素可達 2³¹-1，但我們只比較是否等於 0、不做加法乘法，所以沒有整數溢位風險。We only compare to 0, never arithmetic — no overflow.