Given an m x n matrix, wherever a value is 0, set that value's entire row and entire column to 0. Return the resulting matrix. All zeroing decisions are based on where the zeros were in the ORIGINAL matrix — a cell zeroed by this rule does not itself trigger further zeroing. The classic asks for this in place with O(1) extra space; that technique is the follow-up worth knowing.
Examples
Example 1:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Example 2:
Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Example 3:
Input: matrix = [[1,2],[3,4]]
Output: [[1,2],[3,4]]
Example 4:
Input: matrix = [[0]]
Output: [[0]]
Constraints
1 <= m, n <= 20
-100 <= matrix[i][j] <= 100
Prerequisites
Index arithmetic on a grid, and the discipline of writing the coordinate rule down before coding it.
How to think about it
1. Record First, Rewrite Second Optimal
Intuition
The trap is cascading: zero a row as you find it and the zeros you just wrote look like original zeros, wiping the whole matrix. Two passes fix it — decide everything from the ORIGINAL grid, then apply. The O(1)-space follow-up stores those same flags in the matrix's own first row and column, with two scalars covering the first row and column themselves.
Algorithm
1. Record which rows and which columns contain a zero. 2. Build the result: a cell is zero when its row or column was recorded.
Time & Space
Time O(m x n). Space O(m + n) for the flags — O(1) with the first-row-and-column trick.