Set Matrix Zeroes
Set Matrix Zeroes is a medium Math & Geometry problem from the Blind 75. The key pattern is in-place markers, and a good solution runs in O(m · n) time.
Problem
If a cell is zero, set every cell in its row and column to zero and return the final matrix.
Examples
Example 1
Input
[[1,2,0],[4,5,6],[7,8,9]]Output
[[0,0,0],[4,5,0],[7,8,0]]Example 2
Input
[[1,1,1],[1,0,1],[1,1,1]]Output
[[1,0,1],[0,0,0],[1,0,1]]Example 3
Input
[[0,2,3,0],[4,5,6,7],[8,9,1,2]]Output
[[0,0,0,0],[0,5,6,0],[0,9,1,0]]Approach
Use the first row and first column as flags for which rows and columns to clear, with two extra booleans for the first row and column themselves.
| Pattern | In-place markers |
|---|---|
| Time | O(m · n) |
| Space | O(1) |
Watch out for
Clear the first row and column last, or the markers are destroyed early.