Today’s problem

https://leetcode.com/problems/set-matrix-zeroes/

Intuition

This question asks us to change the rows and columns to 0 if there exists an 0 in the row or column. Therefore, we can store the rows and columns and then change all these rows and colums to zero.

Approach

  1. Store all the columns and rows that contains 0
  2. Change all these columns and rows

Complexity

  • Time complexity: $O(N \times M)$, N is the length of the array, M is the width of the array.

  • Space complexity: $O(N \times M)$, N is the length of the array, M is the width of the array.

Code

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

        change_row_idx = set([])
        change_col_idx = set([])
        # Note that here I use set to avoid recording the same row or column multiple times.

        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    change_row_idx.add(i)
                    change_col_idx.add(j)
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if i in change_row_idx or j in change_col_idx:
                    matrix[i][j] = 0

For more solutions, please visit My blog