Teaching Kids Programming – Set Matrix Zeroes

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Algorithm to Set Matrix to Zeros in Place

We need to go through the elements in the matrix and remember the rows and columns that have the zeros. We can push a tuple of (row, col) coordinate into a queue/array/list so that we can come back setting matrix elements to zeros for those rows or columns. The space complexity is O(RC) because in worst cases every element in the matrix is zero.

We could improve the space complexity to O(R+C) so that we use two sets to remember the “unique” rows and sets. The time complexity is O(RC) as we need to iterate the matrix twice.

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        if not matrix:
            return
        rows = len(matrix)
        cols = len(matrix[0])
        rr = set()
        cc = set()
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 0:
                    rr.add(r)
                    cc.add(c)
        for r in range(rows):
            for c in range(cols):
                if r in rr or c in cc:
                    matrix[r][c] = 0                    

–EOF (The Ultimate Computing & Technology Blog) —