73.Set_Matrix_Zeroes(Medium).md

73. Set Matrix Zeroes (Medium)

Date and Time: Jul 14, 2024, 22:09 (EST)

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

Question:

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

You must do it in place.

Example 1:

Input: matrix = [ [1,1,1],[1,0,1],[1,1,1] ]

Output: [ [1,0,1],[0,0,0],[1,0,1] ]

Explanation:

Example 2:

Input: matrix = [ [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] ]

Constraints:

• m == matrix.length

• n == matrix[0].length

• 1 <= m, n <= 200

• $-2^{31}$ <= matrix[i][j] <= $2^{31} - 1$

KeyPoints:

The first solution takes $O(n)$ space complexity, which we use cols, zero to keep track of if r should be set to 0 or not, and cols() to keep track of if the columns should be set to 0. Then we use for loop to traverse back to set the entry's previous row's elements and column's elements to 0.

The second optimized solution uses only O(1) space complexity.

My Solution:

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        cols = set()
        for r in range(len(matrix)):
            zero = None
            for c in range(len(matrix[0])):
                if matrix[r][c] == 0:
                    zero = True
                    cols.add(c)
                    for i in range(0, c + 1):
                        matrix[r][i] = 0
                    for i in range(0, r + 1):
                        matrix[i][c] = 0
                else:
                    if zero == True:
                        matrix[r][c] = 0
                    elif c in cols:
                        matrix[r][c] = 0

Time Complexity: $O(m * n)$
Space Complexity: $O(n)$

Optimized Solution:

In this version, we follow the hints "use the first cell of every row and column as a flag", like Example 1 for the 0 in the center we will set [1, 0] (the second row), [0, 1] (the second column) to be zero. Then we will traverse the first row to check for which columns need to be set to 0, and the first column to check which rows need to be set to 0.

Note like Example 2, we need to pay attention to if there is 0 in the first row, which will set all the columns to be zero, which are not what we want.

[[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
[[0, 0, 0, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # If matrix[r][c] == 0, set [r][0] = 0 except 1st row, [0][c] = 0
        # Then fill zero for rows and cols
        rowZero = False
        for r in range(len(matrix)):
            for c in range(len(matrix[0])):
                if matrix[r][c] == 0:
                    if r > 0:
                        matrix[r][0] = 0
                    else:
                        rowZero = True
                    matrix[0][c] = 0
        # Fill 0s for each rows
        for r in range(1, len(matrix)):
            if matrix[r][0] == 0:
                for c in range(len(matrix[0])):
                    matrix[r][c] = 0
        # Fill 0s for each cols
        for c in range(len(matrix[0])):
            if matrix[0][c] == 0:
                for r in range(len(matrix)):
                    matrix[r][c] = 0
        # Lastly handle rowZero case
        if rowZero:
            for c in range(len(matrix[0])):
                matrix[0][c] = 0

Time Complexity: $O(m * n)$
Space Complexity: $O(1)$