DSA problem
Set Matrix Zeroes
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0. You must do it in-place.
The naive idea of zeroing rows and columns as you scan is incorrect: the zeros you write would be re-read by later iterations and incorrectly trigger additional rows and columns to be cleared. A correct but memory-heavy fix is to first record every (row, col) pair that should be zeroed, then apply them in a second pass. That approach costs O(m + n) extra space if you store row and column flags separately.
The challenge is to achieve the same result using O(1) extra space. The key observation is that the matrix itself can store the bookkeeping. We use the first cell of each row and each column as a marker: if matrix[i][j] is 0, we set matrix[i][0] and matrix[0][j] to 0. The first row and first column thus encode which rows and columns must be cleared.
The intuition for the optimal approach is to treat row 0 and column 0 as marker arrays. Because cell (0,0) is shared by both markers, we need one extra boolean to remember whether the first column itself contained a zero. We scan the rest of the matrix to set markers, then apply the markers from the inside out, and finally handle the first row and first column separately to avoid them clobbering their own marker bits.
Examples
matrix = [[1,1,1],[1,0,1],[1,1,1]][[1,0,1],[0,0,0],[1,0,1]]matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]][[0,0,0,0],[0,4,5,0],[0,3,1,0]]matrix = [[5]][[5]]Constraints
- m == matrix.length
- n == matrix[0].length
- 1 <= m, n <= 200
- -2^31 <= matrix[i][j] <= 2^31 - 1
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.