class Solution {
public:
    void setZeroes(vector>& matrix) {
        // Treat the first row and column as the flag row and flag column
        // which keeps track of which column or row to mark with zeros
        const int numRows = matrix.size();
        const int numCols = matrix[0].size();

        // The overlapping cell of column 0
        int col0 = 1;

        // Iterate over the matrix once, and mark the rows or columns
        for(int i = 0; i < numRows; i++) {
            for(int j = 0; j < numCols; j++) {
                // Not of our intereset
                if(matrix[i][j] != 0) continue; 
                // Then, mark this row/column as marked

                // This is the first col of the matrix, keeping track of rows
                matrix[i][0] = 0;
                // This is the first row of the matrix, keeping track of columns
                if(j != 0) 
                    matrix[0][j] = 0;
                else
                    col0 = 0;
            }
        }

        // Iterate over once more and mark zeros
        // Go from the other corner of the matrix
        for(int i = numRows-1; i > 0; i--) {
            for(int j = numCols-1; j > 0; j--) {
                // Either if the column flag is on, or row flag is on
                if(matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            }
        }

        // Check and mark the first column and row
        if(matrix[0][0] == 0) {
            for(int j = 0; j < numCols; j++) matrix[0][j] = 0;
        }
        if(col0 == 0) {
            for(int i = 0; i < numRows; i++) matrix[i][0] = 0;
        }
    }
};