73. Set Matrix Zeroes

73. Set Matrix Zeroes

 

https://youtu.be/DdwGGU5LGdA?si=ciihM075wd64ohnV

 

# zeros = [] 배열 사용 => 시간 복잡도: O(m*n), 공간 복잡도 O(m*n)

 

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 시간 복잡도: O(m*n), 공간 복잡도 O(m*n)
        zeros = []
        for r in range(len(matrix)):
            for c in range(len(matrix[0])):
                if matrix[r][c] == 0:
                    zeros.append((r,c))

        for r, c in zeros:
            for i in range(len(matrix)):
                matrix[i][c] = 0
            
            for j in range(len(matrix[0])):
                matrix[r][j] = 0

 

# zeros_rows = set(), zeros_cols = set(), 집합 사용 => 시간 복잡도: O(m*n), 공간 복잡도 O(m + n),

   - 공간 복잡도 O(m + n) 로 개선

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 시간 복잡도: O(m*n), 공간 복잡도 O(m*n) -> O(m + n) 으로 개선 
        zero_rows = set()  # 0 인 row 인덱스 저장
        zero_cols = set()  # 0 인 col 인덱스 저장

        for r in range(len(matrix)):
            for c in range(len(matrix[0])):
                if matrix[r][c] == 0:
                    zero_rows.add(r)
                    zero_cols.add(c)

        for r in zero_rows:
            for i in range(len(matrix[0])):
                matrix[r][i] = 0
            
        for c in zero_cols:
            for i in range(len(matrix)):
                matrix[i][c] = 0

 

# first_row_zero, first_col_zero,  변수 사용 => 시간 복잡도: O(m*n), 공간 복잡도 O(1),

   - 공간 복잡도 O(1) 로 개선

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 시간 복잡도: O(m*n), 공간 복잡도 O(m*n) -> O(m + n) -> O(1) 으로 개선 

        # any: 하나라도 0 있으면 True, 아니면, False
        first_row_zero = any(matrix[0][c] == 0 for c in range(len(matrix[0]))) 
        first_col_zero = any(matrix[r][0] == 0 for r in range(len(matrix)))

        # index == 1의 경우는 위에 초기값에서 순회했음
        for r in range(1, len(matrix)): 
            for c in range(1, len(matrix[0])):
                if matrix[r][c] == 0:
                    matrix[r][0] = 0
                    matrix[0][c] = 0

        for r in range(1, len(matrix)): 
            for c in range(1, len(matrix[0])):
                if matrix[r][0] == 0 or matrix[0][c] == 0:
                    matrix[r][c] = 0

        if first_row_zero:
            for i in range(len(matrix[0])):
                matrix[0][i] = 0
            
        if first_col_zero:
            for i in range(len(matrix)):
                matrix[i][0] = 0