MediumBlind75MatrixHash Table

Set Matrix Zeroes

Given an m x n matrix, if an element is 0, set its entire row and column to 0's. Do it in-place.

Examples

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

The element at (1,1) is 0, so row 1 and column 1 are set to 0.

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

Elements at (0,0) and (0,3) are 0.

Constraints

  • •m == matrix.length
  • •n == matrix[0].length
  • •1 <= m, n <= 200
  • •-2^31 <= matrix[i][j] <= 2^31 - 1

Approaches

Use sets to record which rows and columns contain zeros.

CodeT: O(m * n) | S: O(m + n)
def set_zeroes(matrix):
    rows = set()
    cols = set()
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == 0:
                rows.add(i)
                cols.add(j)
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if i in rows or j in cols:
                matrix[i][j] = 0

Use the first row and column as markers.

CodeT: O(m * n) | S: O(1)
def set_zeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_zero = any(matrix[i][0] == 0 for i in range(m))
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0
    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0

Same approach with cleaner implementation.

Diagram

matrix = [[1,1,1],[1,0,1],[1,1,1]] First row/col markers: matrix[0][1]=0, matrix[1][0]=0 Mark zeros: set entire row 1 and col 1 to 0 Result: [[1,0,1],[0,0,0],[1,0,1]]
CodeT: O(m * n) | S: O(1)
def set_zeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    is_first_row_zero = 0 in matrix[0]
    is_first_col_zero = 0 in [matrix[i][0] for i in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    if is_first_row_zero:
        for j in range(n):
            matrix[0][j] = 0
    if is_first_col_zero:
        for i in range(m):
            matrix[i][0] = 0

Complexity Comparison

Extra Space
T: O(m * n)S: O(m + n)

Use sets to record which rows and columns contain zeros.

In-Place - First Row/Col Markers
T: O(m * n)S: O(1)

Use the first row and column as markers.

Optimized In-Place
T: O(m * n)S: O(1)

Same approach with cleaner implementation.

Common Mistakes

Not handling the first row and column separately

Using extra space when O(1) is required

Overwriting markers before they are used

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems