Set Matrix Zeroes(73)


Medium - Hash Table


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.

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?
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        row = []
        col = []
        
        # 0이 존재하는 위치의 row, col을 추출하자
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if matrix[i][j] == 0:
                    if row.count(i) == 0:
                        row.append(i)
                    if col.count(j) == 0:
                        col.append(j)
        
        for i in row: # row 처리
            matrix[i] = [0] * len(matrix[0])
                 
        for i in range(len(matrix)): # col 처리
            for j in col:
                matrix[i][j] = 0
            
        return matrix