Set Matrix Zeroes

Medium· in-place· markers

Problem

Whenever a cell of an m × n matrix is 0, its entire row and column must become 0. Modify the matrix in place, ideally using only constant extra space.

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

Constraints

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

Hints & approach

Hint 1

Zeroing immediately destroys information you still need.

Hint 2

Record which rows and columns to clear first — O(m + n) space works.

Hint 3

Use the first row and first column themselves as the markers, plus one flag for the first column.

Approachtry the hints first

Scan the matrix and, for each zero at (i, j), set matrix[i][0] and matrix[0][j] to 0 as markers; keep a separate flag for whether column 0 itself must be cleared, because matrix[0][0] is shared. Then clear inner cells whose row or column marker is 0, working from the bottom-right so markers are read before they are overwritten. Finally clear the first row if matrix[0][0] is 0 and the first column if the flag is set.

Time O(m·n) · Space O(1)

← PreviousSpiral Matrix Next →Search a 2D Matrix