Set Matrix Zeroes

Problem Statement

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

You must update the matrix in-place.

Follow up: Could you solve it using O(1) space?

Example 1:

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


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

Example 2:

Input: matrix = [
  [1,2,3],
  [4,0,5],
  [6,7,8]
]


Output: [
  [1,0,3],
  [0,0,0],
  [6,0,8]
]

Constraints:

  • 1 <= matrix.length, matrix[0].length <= 100
  • -2^31 <= matrix[i][j] <= (2^31) - 1

You should aim for a solution with O(m * n) time and O(1) space, where m is the number of rows and n is the number of columns.

Hint 1

Consider using the first row and first column of the matrix to store information about which rows and columns should be zeroed out.

Hint 2

Be careful to handle the case where the first row or column itself contains a zero. You may need to use an additional variable to track this.

Solution

Brute Force

def set_zeroes_brute_force(matrix: List[List[int]]) -> None:
    rows, cols = len(matrix), len(matrix[0])
    mark = [[matrix[r][c] for c in range(cols)] for r in range(rows)]


    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == 0:
                for col in range(cols):
                    mark[r][col] = 0
                for row in range(rows):
                    mark[row][c] = 0


    for r in range(rows):
        for c in range(cols):
            matrix[r][c] = mark[r][c]

Time complexity: O(m * n) Space complexity: O(m * n)

Where m is the number of rows and n is the number of columns.