Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

O(mn) sol

We can use a list to hold all the positions that have 0 in it. Because there could be O(mn) 0 in the list, this solution will take O(mn) space

O(m + n) space

Because there are only m + n rows and columns, we can just record the rows and columns that need to be emptied.

def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        This is very similar to a previous problem
        I think it is find the smallest number that's out of line
        O(mn): create a list to hold position of 0 entry
        """
        zeros_r = {}
        zeros_c = {}
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    zeros_r[i] = i
                    zeros_c[j] = j
        for key in zeros_r:
            for i in range(len(matrix[0])):
                matrix[key][i] = 0
        for col in zeros_c:
            for i in range(len(matrix)):
                matrix[i][col] = 0

Constant space

The need to memorize what columns and rows we need to delete

We can not just delete the column and row when we see a zero. So the need to store them are HARD.

Use first row and first column to store if a row and column needs to be zeroed.

If matrix[i][j] == 0, then matrix[0][j] = 0 and matrix[i][0] = 0. We later need to zero every entry with [?][j] and entry with [i][?].

In the first row, if an entry matrix[0][j] is 0, that means every entry in column j will be zero.
In the first column, matrix[i][0], if matrix[i][0] = 0 then every entry in row i will be 0

Need to use a variable to record what happened with first column

Based on the rule above, matrix[0][0] will be 0 if either first column or first row becomes 0. We can use another variable to hold whether first col is zero and use matrix[0][0] to record information abot the first row.

CAUTION!!! Since we are checking first col separately, we need to check the for loop as well.

zero from bottom right to top left

Since we use first row and first column to store information, we want to zero them out LAST. So we start from the bottom right.

public:void setZeroes(vector<vector<int> > &matrix) {
    int col0 = 1, rows = matrix.size(), cols = matrix[0].size();
    for(int i = 0; i < rows; i ++){
        if (matrix[i][0] == 0) col0 = 0; 
        for( int j = 1; j < cols; j ++){
            if (matrix[i][j] == 0)
                matrix[i][0] = matrix[0][j] = 0;
        }
    }

    for(int i = rows - 1; i >= 0; i --){
        for(int j = cols - 1; j >= 1; j --){
            if (matrix[i][0] == 0 or matrix[0][j] ==0){
                matrix[i][j] = 0;
            }   
        }
        if (col0 == 0) matrix[i][0] = 0;
    }
}

Bugs

Starting column at 1

Because we take care of the first column outside of the nested for loop, if we start column scan at 0, and see an entry in the first column to be 0, then we will set matrix[0][0] to zero, but matrix[0][0] stores whether the first row should be cleared. It will leads to error.

EG

1 1 1 
0 1 1 
1 1 1

If we scan from the column 0, then it will flip matrix[0][0] to 0 and when we reconstruct the new matrix we will get

0 0 0 
0 0 0 
0 1 1