Set Matrix Zeroes
The problem
If any entry in a rectangular matrix is zero, make its entire row and column zero. Perform the update in place using constant auxiliary space.
Example
[[1, 0], [3, 4]] → [[0, 0], [3, 0]]
Need a hint?
The first row and column can store markers, but their original zero status must be saved.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Record whether the first row and first column originally contain a zero. Scan the interior and mark affected rows/columns in those first edges. Zero the interior from the markers, then update the first row and column using their saved flags.
Complexity
O(mn) time and O(1) auxiliary space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.