Set Matrix Zeroes

The key idea

Record which rows and columns must be zeroed BEFORE you write any zero, otherwise a zero you write is mistaken for an original zero and wrongly wipes more rows and columns. Use the matrix's own first row and first column as the marker storage to reach O(1) extra space.

Problem

You are given an m x n integer matrix matrix. If an element is 0, set its entire row and its entire column to 0. You must do it in place, modifying matrix directly. The hard part is that as you write zeros you must not confuse a freshly written 0 with an original 0 — so the rows and columns to clear have to be decided from the original values first.

Constraints

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1

Examples

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]]

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]]

Complexity

Time: O(m*n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →