Big O Practice: Set Matrix Zeroes

def set_zeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    first_row_zero = 0 in matrix[0]
    first_col_zero = any(row[0] == 0 for row in matrix)
    for r in range(1, m):
        for c in range(1, n):
            if matrix[r][c] == 0:
                matrix[r][0] = 0
                matrix[0][c] = 0
    for r in range(1, m):
        for c in range(1, n):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0
    if first_row_zero:
        for c in range(n):
            matrix[0][c] = 0
    if first_col_zero:
        for r in range(m):
            matrix[r][0] = 0

Variables

• m - number of rows in the matrix
• n - number of columns in the matrix

Explanation

A constant number of passes over the grid - **O(m · n)** time. By using the first row and column as marker storage we avoid the O(m + n) auxiliary array, achieving **O(1)** auxiliary space.

More Big O practice problems · Today's daily problem