LC 0073 [M] Set Matrix Zeroes - ALawliet/algorithms GitHub Wiki

https://www.youtube.com/watch?v=T41rL0L3Pnw&ab_channel=NeetCode

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # O(1)
        ROWS, COLS = len(matrix), len(matrix[0])
        rowZero = False # need an extra variable because (0,0) could be row or col and we use col, and we want no overlaps
        
        # determine which rows/cols need to be 0
        # embed the m + n - 1 + 1 memory into the existing array
        # it is ok because by the time we update it we have visited that square already
        for r in range(ROWS):
            for c in range(COLS):
                if matrix[r][c] == 0:
                    matrix[0][c] = 0
                    if r > 0:
                        matrix[r][0] = 0
                    else:
                        rowZero = True
        
        # zero out most of them
        for r in range(1, ROWS):
            for c in range(1, COLS):
                if matrix[0][c] == 0 or matrix[r][0] == 0:
                    matrix[r][c] = 0
               
        # zero out first col
        if matrix[0][0] == 0:
            for r in range(ROWS):
                matrix[r][0] = 0
                
        # zero out first row
        if rowZero:
            for c in range(COLS):
                matrix[0][c] = 0