73. Set Matrix Zeroes

Description:

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's, and return the matrix.

You must do it in place.

 

'''
[1] naive - using additional table)


additional=[[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]

# set 1, if mat[row][col]==0
for row in range(len(matrix)):
    for col in range(len(matrix[row])):
        if matrix[row][col]==0:
            additional[row][col]=1

for i in range(len(matrix)):
    for j in range(len(matrix[i])):
        if additional[i][j]==1:
            
            for col in range(len(matrix[0])):
                matrix[i][col]=0
            for row in range(len(matrix)):
                matrix[row][j]=0

return matrix

- T/C: O(m*n*(m+n)) # if all elements of matrix are 0
- S/C: O(m*n)   # for additional matrix
'''

'''
[2] using set)

because the entire row(or col) should be 0, keep row and col where matrix[row][col]==0

ROW=len(matrix)
COL=len(matrix[0])

rows=set()
cols=set()

for i in range(ROW):
    for j in range(COL):
        if matrix[i][j]==0:
            rows.add(i)
            cols.add(j)

for i in range(ROW):
    for j in range(COL):
        if i in rows or j in cols:
            matrix[i][j]=0


- T/C: O(m*n)
- S/C: O(m+n)  #for two sets
'''

'''
[3] flag )

using first row and first col as flag

if matrix[i][j]==0:
    matrix[i][0]=0
    matrix[0][j]=0
    
and then, traversal matrix and set matrix zeros
* matrix[0][0] is special. the whole elements of matrix could be zeros, if considering matrix[0][0](==0) at the first
* so, should be treat first row and first col at the last time.
* and, it is needed to record wheter first_row and first_col need to be set zero or not

m=len(matrix)
n=len(matrix[0])

first_row=False
first_col=False
for i in range(m):
    for j in range(n):
        if matrix[i][j]==0:
            matrix[i][0]=0
            if i==0:
                first_row=True
            matrix[0][j]=0
            if j==0:
                first_col=True
            
for i in range(1,m):
    if matrix[i][0]==0:
        for j in range(n):
            matrix[i][j]=0

for j in range(1,n):
    if matrix[0][j]==0:
        for i in range(m):
            matrix[i][j]=0

if first_row:
    for i in range(n):
        matrix[0][i]=0
                
if first_col:
    for i in range(m):
        matrix[i][0]=0


- T/C: O(m*n)
- S/C: O(1)
'''


class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m=len(matrix)
        n=len(matrix[0])

        first_row=False
        first_col=False
        for i in range(m):
            for j in range(n):
                if matrix[i][j]==0:
                    matrix[i][0]=0
                    if i==0:
                        first_row=True
                    matrix[0][j]=0
                    if j==0:
                        first_col=True
            
        for i in range(1,m):
            if matrix[i][0]==0:
                for j in range(n):
                    matrix[i][j]=0

        for j in range(1,n):
            if matrix[0][j]==0:
                for i in range(m):
                    matrix[i][j]=0

        if first_row:
            for i in range(n):
                matrix[0][i]=0
                
        if first_col:
            for i in range(m):
                matrix[i][0]=0