Cracking the Coding Interview - Clear Rows and Columns

1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0

As Gayle states, this problem looks deceptively simple. Just iterate through the matrix, and set the rows and columns to zero! But by doing that, you may be overwriting non-zero values.

Unless you plan on preserving the values in the original matrix and move updated values to a new matrix, you can’t solve this with a single pass through the matrix.

Without creating a new matrix, one solution is to do two passes. The first pass figures out which rows and columns should be cleared without making any changes to the matrix. The second pass performs the cell updates.

Track affected rows and columns using a set

def clear_matrix(matrix):
    rows, cols  = len(matrix), len(matrix[0])
    target_rows, target_cols = set(), set()
    for row in range(rows):
        for col in range(cols):
            value = matrix[row][col]
            if value == 0:
                target_rows.add(row)
                target_cols.add(col)
    for row in range(rows):
        for col in range(cols):
            if row in target_rows or col in target_cols:
                matrix[row][col] = 0
    return matrix

This solution requires O(M + N) additional space and the runtime is O(M * N).

Track affected rows and columns using an integer as bit vector

def clear_matrix(matrix):
    rows, cols  = len(matrix), len(matrix[0])
    target_rows, target_cols = 0, 0
    for row in range(rows):
        for col in range(cols):
            value = matrix[row][col]
            if value == 0:
                target_rows |= (1 << row)
                target_cols |= (1 << col)
    for row in range(rows):
        for col in range(cols):
            if ((1 << row & target_rows) > 0) or (( 1 << col & target_cols) > 0):
                matrix[row][col] = 0
    return matrix

This solution cuts down on the space by using an integer as a bit vector instead of set data structures.