Striver’s sde sheet day 1 problem 1

Problem Statement: Given a matrix if an element in the matrix is 0 then you will have to set its entire column and row to 0 and then return the matrix

Naive solution,with runtime O(n**2) and space also O(n)

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])
        #print(m,n)
        a=set()
        for i in range(0,m):
            for j in range(0,n):
                if matrix[i][j]==0:
                    a.add((i,j))
        #print(a)
        for x in a:
            p=x[0]
            q=x[1]
            for j in range(0,n):
                matrix[p][j]=0
            for i in range(0,m):
                matrix[i][q]=0

Now for the optimal solution

def zeroMatrix(matrix, n, m):
    row = [0] * n  # row array
    col = [0] * m  # col array

    # Traverse the matrix:
    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 0:
                # mark ith index of row wih 1:
                row[i] = 1

                # mark jth index of col wih 1:
                col[j] = 1

    # Finally, mark all (i, j) as 0
    # if row[i] or col[j] is marked with 1.
    for i in range(n):
        for j in range(m):
            if row[i] or col[j]:
                matrix[i][j] = 0

    return matrix

if __name__ == "__main__":
 matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
 n = len(matrix)
 m = len(matrix[0])
 ans = zeroMatrix(matrix, n, m)

 print("The Final matrix is:")
 for row in ans:
     for ele in row:
         print(ele, end=" ")
     print()