Set matrix zeroes

Problem If any element of an m x n matrix is 0, set its entire row and column to 0 — in place.

Input / Output

• Input: int matrix. Output: matrix mutated in place.

Constraints

• m, n up to 200; the ask escalates by space: O(m+n) extra is easy, O(1) extra is the real question.

Example

• [[1,1,1],[1,0,1],[1,1,1]] → [[1,0,1],[0,0,0],[1,0,1]].

Expected approach

• O(m+n): record zero rows/columns in two boolean arrays, then wipe. O(1): use row 0 and column 0 themselves as the marker arrays — first save whether they originally contain zeros in two scalars, mark zeros into the borders, wipe interior from the markers, finally wipe the borders from the scalars. Ordering matters (wipe borders last). The naive trap — zeroing as you scan — cascades false zeros; explain why. O(m*n) time.