73. Set Matrix Zeroes (Array, Hash Table, Matrix)

링크 - https://leetcode.com/problems/set-matrix-zeroes/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

이 방법은 두개의 set()을 두고 풀면 아주 쉬운 문제이기 때문에 O(1) space complexity를 갖는 해결법을 알아보자.

우리는 첫번째 row와 col를 set()대신 indicator로 사용할 수 있다. 다시말해, row나 col에 0이 있으면, 거기에 해당되는 맨 처음 원소를 0으로 설정하는 것이다.

Code

class Solution(object):
    def setZeroes(self, matrix: List[List[int]]) -> None:
        is_col = False
        R = len(matrix)
        C = len(matrix[0])
        for i in range(R):
            # Since first cell for both first row and first column is the same i.e. matrix[0][0]
            # We can use an additional variable for either the first row/column.
            # For this solution we are using an additional variable for the first column
            # and using matrix[0][0] for the first row.
            if matrix[i][0] == 0:
                is_col = True
            for j in range(1, C):
                # If an element is zero, we set the first element of the corresponding row and column to 0
                if matrix[i][j] == 0:
                    matrix[0][j] = 0
                    matrix[i][0] = 0

        # Iterate over the array once again and using the first row and first column, update the elements.
        for i in range(1, R):
            for j in range(1, C):
                if not matrix[i][0] or not matrix[0][j]:
                    matrix[i][j] = 0

        # See if the first row needs to be set to zero as well
        if matrix[0][0] == 0:
            for j in range(C):
                matrix[0][j] = 0

        # See if the first column needs to be set to zero as well
        if is_col:
            for i in range(R):
                matrix[i][0] = 0

Complexity

Time Complexity: O(m x n) 여기서 m과 n은 각각 matrix의 row와 col의 개수이다.

Space Complexity: O(1)