Set Matrix Zeroes
MediumGiven an m x n integer matrix, whenever an element is 0, set its entire row and column to 0. Modify matrix in place. The function doesn't return anything.
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]]
The two zeros in the first row clear the first row and the first and last columns.
Constraints
1 <= m, n <= 200-2^31 <= matrix[i][j] <= 2^31 - 1
Approach
The straightforward solution records which rows and columns contain a zero in two sets, then clears every cell whose row or column is in a set. That takes O(m + n) extra space. To get down to O(1), store the same record inside the matrix: the first cell of each row marks whether that row needs clearing, and the first cell of each column marks whether that column does. The first row and first column are now holding markers, so before you overwrite anything, note whether they contained a zero originally, and clear them last.
Steps
- Record whether the first row and the first column contain a zero.
- For every other cell that's
0, setmatrix[r][0]andmatrix[0][c]to0. - For every cell outside the first row and column, set it to
0if its row marker or column marker is0. - Clear the first row and the first column if step 1 found a zero in them.
Complexity
- Time:
O(m · n). A constant number of passes over the matrix. - Space:
O(1). Two flags.
Common mistakes
- Clearing rows and columns as soon as you find a zero. The new zeros trigger more clearing, until most of the matrix is
0. - Clearing the first row or first column before using their markers. That wipes out the record you still need for the rest of the matrix.
Interview experiences
1 sharedRelated questions
01 MatrixRelated courses



