**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.