Given an m × n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Before you code
Zeroing as you scan is wrong: the zeros you write look like original zeros and spread across the whole matrix. You need to record which rows and columns to clear before clearing any. The question is where to keep that record.
Hints
- Easy version: two boolean arrays of sizes m and n. That is O(m + n) extra space.
- O(1) version: use the first row and first column of the matrix itself as those two arrays.
- The first row and column then need their own flags, because their markers overlap at
matrix[0][0]. Record whether each originally contained a 0 before using them as markers. - Clear the inner cells first, and the first row and column last.
Production & complexity notes
When solving Set matrix zeroes on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Space and hidden costs to reinforce the underlying pattern.
What it practices
Measuring and reducing extra space, from Space and hidden costs.