Zero Striping
Given an m x n integer matrix, if an element is 0, set its entire
row and column to 0. You must do this in place, modifying the
input matrix directly.
Example 1
Input:
[[1, 1, 1],
[1, 0, 1],
[1, 1, 1]]
Output:
[[1, 0, 1],
[0, 0, 0],
[1, 0, 1]]
Example 2
Input:
[[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]]
Constraints
1 <= m, n <= 200-2^31 <= matrix[i][j] <= 2^31 - 1
The tricky part is that if we zero out cells as soon as we find a
0, we create new zeros that could be mistaken for original zeros
on a later pass, cascading incorrectly across the whole matrix.
The fix is to separate "detection" from "mutation." First scan the whole matrix and record, in two hash sets, which row indices and which column indices contain at least one original zero. Only after that full scan do we make a second pass over every cell and zero it out if its row or column is in the recorded sets. Because the sets are built entirely from the original data before any mutation happens, there's no cascading.
def zero_striping(matrix: list[list[int]]) -> None:
m, n = len(matrix), len(matrix[0])
zero_rows: set[int] = set()
zero_cols: set[int] = set()
for r in range(m):
for c in range(n):
if matrix[r][c] == 0:
zero_rows.add(r)
zero_cols.add(c)
for r in range(m):
for c in range(n):
if r in zero_rows or c in zero_cols:
matrix[r][c] = 0
Complexity: O(m * n) time, since we make two full passes over the matrix. O(m + n) extra space for the row and column sets (this can be optimized further to O(1) using the matrix's own first row/column as markers, but the two-set approach is simpler to reason about and still linear).
Share this question