POTD #5 - Set Matrix Zeroes | Geeks For Geeks

Problem Statement

Geeks For Geeks : https://www.geeksforgeeks.org/problems/set-matrix-zeroes/1

You are given a 2D matrix mat[][] of size n×m. The task is to modify the matrix such that if mat[i][j] is 0, all the elements in the i-th row and j-th column are set to 0 and do it in constant space complexity.

Input: mat[][] = [[1, -1, 1],
                [-1, 0, 1],
                [1, -1, 1]]
Output: [[1, 0, 1],
        [0, 0, 0],
        [1, 0, 1]]
Explanation: mat[1][1] = 0, so all elements in row 1 and column 1 are updated to zeroes.

Input: mat[][] = [[0, 1, 2, 0],
                [3, 4, 5, 2],
                [1, 3, 1, 5]]
Output: [[0, 0, 0, 0],
        [0, 4, 5, 0],
        [0, 3, 1, 0]]
Explanation: mat[0][0] and mat[0][3] are 0s, so all elements in row 0, column 0 and column 3 are updated to zeroes.

My Approach

1. Iterate through the matrix and check whether mat[i][j] is zero. If its zero then row i and col j need to made as zeros.
2. Collect them in a set
3. Finally iterate through the set and update the matrix.

#User function Template for python3
class Solution:
    
    
    def setMatrixZeroes(self, mat):
        rows_to_zeros = set()
        cols_to_zeros = set()
        
        rows = len(mat)
        cols = len(mat[0])
        
        for i in range(rows):
            for j in range(cols):
                if mat[i][j] == 0:
                    rows_to_zeros.add(i)
                    cols_to_zeros.add(j)
        
        for row in rows_to_zeros:
            for itr in range(cols):
                mat[row][itr] = 0
        
        
        for col in cols_to_zeros:
            for itr in range(rows):
                mat[itr][col] = 0       
        
        return mat