class Solution:
    # Time: O(rows * cols) - space: O(1)
    def fill_zeroes(self, matrix):
        rows_count, col_count = len(matrix), len(matrix[0])
        for row in range(rows_count):
            for col in range(col_count):
                if not matrix[row][col]:
                    matrix[row][col] = 'X'
                    self.fill_row(row, 'X', matrix)
                    self.fill_col(col, 'X', matrix)
        
        for row in range(rows_count):
            for col in range(col_count):
                if matrix[row][col] == 'X':
                    matrix[row][col] = 0
    
    def fill_row(self, row, val, matrix):
        col_count = len(matrix[0])
        for col in range(col_count):
            matrix[row][col] = val
    
    def fill_col(self, col, val, matrix):
        row_count = len(matrix)
        for row in range(row_count):
            matrix[row][col] = val
    
    def print_matrix(self, matrix):
        for row in matrix:
            print(row)
    
    def fill_zeroes2(self, matrix):
        should_fill_row, should_fill_col = False, False
        rows_count, col_count = len(matrix), len(matrix[0])
        
        for row in range(rows_count):
            for col in range(col_count):
                if not matrix[row][col]:
                    if row == 0:
                        should_fill_row = True
                    if col == 0:
                        should_fill_col = True
                    matrix[0][col] = 0
                    matrix[row][0] = 0
        
        for row in range(1, rows_count):
            for col in range(1, rows_count):
                if not matrix[row][0] or not matrix[0][col]:
                    matrix[row][col] = 0
        
        if should_fill_row:
            self.fill_row(0, 0, matrix)
        
        if should_fill_col:
            self.fill_col(0, 0, matrix)


matrix = [[1,0,1,1,1],[1,1,1,1,1],[1,1,1,1,1], [1,1,1,0,1], [1,1,1,1,1]]
solution = Solution()
solution.print_matrix(matrix)
solution.fill_zeroes2(matrix)
print('===============')
solution.print_matrix(matrix)

