Leetcode 73. Set Matrix Zeroes

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]]

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
• -231 <= matrix[i][j] <= 231 - 1

Follow up:

• A straightforward solution using O(mn) space is probably a bad idea.
• A simple improvement uses O(m + n) space, but still not the best solution.
• Could you devise a constant space solution?

1. The easiest way is create a new m*n matrix to zero the coordinates based on the input.
2. O(m + n) is adding a new row and column as flags to indicate whether or not the row or column needs to be zeroed.
3. Final solution is constant space solution. The first element of column or row can be an indicator, but the first row or first column may not need to be all zeroed. Therefore, we can have a 2 flags to indicate that.

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

        n = len(matrix)
        m = len(matrix[0])
        first_row_zero = False
        first_column_zero = False

        for y in range(n):
            for x in range(m):
                if matrix[y][x] == 0:
                    if y == 0:
                        first_row_zero = True
                    if x == 0:
                        first_column_zero = True
                    matrix[0][x] = None
                    matrix[y][0] = None

        for y in reversed(range(n)):
            for x in reversed(range(m)):
                if matrix[y][0] is None or matrix[0][x] is None:
                    if y == 0:
                        if first_row_zero:
                             matrix[y][x] = 0
                        elif matrix[y][x] is None:
                            matrix[y][x] = 0
                    elif x == 0:
                        if first_column_zero:
                            matrix[y][x] = 0
                        elif matrix[y][x] is None:
                            matrix[y][x] = 0
                    else:
                        matrix[y][x] = 0