Set Matrix Zeroes

Problem

You are given an m x n grid of integers. For every cell that contains 0, set the entire row and the entire column containing that cell to 0. Do this in place, and aim for constant extra space.

• The grid can be a few hundred rows and columns.
• Values span the full signed-32-bit range.
• Only zeros present in the original grid trigger clearing; zeros you write during the process must not cascade.

Examples

• [[5,5,5],[5,0,5],[5,5,5]] → [[5,0,5],[0,0,0],[5,0,5]]. The single zero clears row 1 and column 1.
• [[0,2,3,0],[4,5,6,7],[8,9,1,2]] → [[0,0,0,0],[0,5,6,0],[0,9,1,0]]. Two zeros in row 0 clear row 0 and columns 0 and 3.
• [[1,2],[3,4]] → unchanged; no zeros means nothing is cleared.

Hints

1. Why can you not simply scan and zero rows/columns as you find zeros? What does a freshly written zero do to the rest of the scan?
2. Record which rows and which columns must be cleared first, then clear in a second pass. How much space does that need?
3. Use the first row and first column themselves as the record, plus one extra flag for whether the first column should be cleared. Process the interior first and the first row/column last.