73. Set Matrix Zeroes

Check out problem description here

Set Matrix Zeroes - LeetCode

Approach 1:

Using an extra copy of the given matrix. And while iterating the source matrix ,if a cell matrix[i][j] is found to be zero , make the ith row and j th columns zero

Time :O(m*n)

Space:O(m*n)

Approach 2:

Using two set to indicate which rows and columns need to be made as zero.

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        hashrow_=set()
        hashcol_=set()
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j]==0:
                    hashrow_.add(i)
                    hashcol_.add(j)         
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if(i in hashrow_):
                    matrix[i][j]=0
                if(j in hashcol_):
                    matrix[i][j]=0    
        return matrix

Time :O(m*n)

Space:O(m+n)

Approach 3:

The efficient solution.

We can solve the problem using the same matrix. We keep two variables that indicate whether the first row and first column already contain zeros as this row and column will be used to indicate which column and rows contain zeros .First row that is used to indicate which columns contain zeros, ith index. And first column to indicate which rows contain zeros.

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        first_row, first_col=0,0
        for j in range(len(matrix[0])):
            if(matrix[0][j]==0):
                first_row=1
                break     
        for i in range(len(matrix)):
            if(matrix[i][0]==0):
                print(i)
                first_col=1
                break             
        for i in range(1,len(matrix)):
            for j in range(1,len(matrix[0])):
                if(matrix[i][j]==0):
                    matrix[0][j]=0
                    
        for i in range(1,len(matrix)):
            for j in range(1,len(matrix[0])):
                    if(matrix[0][j]==0):
                        matrix[i][j]=0
                    if(matrix[i][0]==0):    
                        matrix[i][j]=0
        if(first_row):
            for j in range(len(matrix[0])):
                matrix[0][j]=0
        if(first_col):
            for i in range(len(matrix)):
                matrix[i][0]=0                  
        return(matrix)

Time :O(m*n)

Space: O(1)