# 73 - Set Matrix Zeroes

解法一 - 先記錄哪些 row 跟 col 要設成 0，再重新設定

這個解法算是很直觀，只是除了花 O(MN) 的時間之外，還得花 O(M+N) 的空間。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        set<int> rows;
        set<int> cols;

        for(int r=0; r<m; r++) {
            for(int c=0; c<n; c++) {
                if(matrix[r][c] == 0) {
                    rows.insert(r);
                    cols.insert(c);
                }
            }
        }

        for(int r=0; r<m; r++) {
            for(int c=0; c<n; c++) {
                if(rows.find(r) != rows.end() || cols.find(c) != cols.end()) {
                    matrix[r][c] = 0;
                }
            }
        }
    }
};

解法二 - 暴力法

首先將應該被改成 0 位置的 value 變成一個在矩陣裡不會出現的值，都設定完之後，再走過一次矩陣把這些值設成 0 就好。必須要這樣做是因為如果在過程中就直接把這些設成 0，那整個矩陣就都得變成 0 了。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int MODIFIED = -10000;
        int m = matrix.size();
        int n = matrix[0].size();

        for(int r=0; r<m; r++) {
            for(int c=0; c<n; c++) {
                if(matrix[r][c] == 0) {
                    for (int k = 0; k < n; k++) {
                        if (matrix[r][k] != 0) {
                            matrix[r][k] = MODIFIED;
                        }
                     }
                     for (int k = 0; k < m; k++) {
                        if (matrix[k][c] != 0) {
                            matrix[k][c] = MODIFIED;
                        }
                     }
                }
            }
        }

        for(int r=0; r<m; r++) {
            for(int c=0; c<n; c++) {
                if(matrix[r][c] == MODIFIED) {
                    matrix[r][c] = 0;
                }
            }
        }
    }
};

這個方法的空間複雜度確實是 O(1)，但因為最糟情況是每一個位置都得把他那個 row 跟 col 的改成 MODIFIED，所以時間複雜度是 O(MN*(M+N))。

解法三 - 用各 row ＆ col 的頭當作 flag 來標記這一個 row 跟 col 要不要設成 0

實作如下：

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) { 
        int m = matrix.size();
        int n = matrix[0].size();
        bool isCol = false;

        for(int r=0; r<m; r++) {
            // Since first cell for both first row and first column is the same 
            // i.e. matrix[0][0]
            // We can use an additional variable for either the first row/column.
            // We use isCol variable for the first column
            // and using matrix[0][0] for the first row.
            if (matrix[r][0] == 0) {
                isCol = true;
            }

            for(int c=1; c<n; c++) {
                if (matrix[r][c] == 0) {
                    matrix[0][c] = 0;
                    matrix[r][0] = 0;
                }
            }
        }

        // We need to start from r = 1 & c = 1
        // because if matrix[0][0] == 0
        // we will set matrix[0][c] to 0 for all c
        // then we will set the whoiel matrix to 0
        for(int r=1; r<m; r++) {
            for(int c=1; c<n; c++) {
                if (matrix[r][0] == 0 || matrix[0][c] == 0) {
                    matrix[r][c] = 0;
                }
            }
        }

        if(matrix[0][0] == 0) {
            for(int c=0; c<n; c++) {
                matrix[0][c] = 0;
            }
        }

        if (isCol) {
            for (int r=0; r<m; r++) {
                matrix[r][0] = 0;
            }
        }
    }
};