Skip to main content

0073 - Set Matrix Zeroes (Medium)

Problem Statement

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

You must do it in place.

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


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

Follow up:

  • A straightforward solution using O(mn) space is probably a bad idea.
  • A simple improvement uses O(m + n) space, but still not the best solution.
  • Could you devise a constant space solution?

Approach 1: Inplace, Constant Space, Iteration.

To save space, we can just iterate over the entire matrix initially, if we ever reach a 00, we can record that in the top row/left column, by rewriting it with a 00. Then we can check the top row, left column at the end, and rewrite all rows/columns that have a top row/left column as 00.

The edge case you can imagine is how we handle the top left corner. If we have a 00 in the first row/first column and place a 00 in the first row/column, then when we replace all numbers afterwards, we are going to ruin our tracking method.

To handle this, we can use a boolean to track if the first row/first column has zeroes, iterate the first/row column, and update the boolean of the first row/column has a 00. From then on, we can do as we described above, just starting at 11 for both the row/column, as we already handled the first row/column.

Finally, we can rewrite everything, again starting at 11 for both the row/column, and handling the first row/column at the end, based on the boolean values we found earlier.

Time Complexity: O(mn)O(m * n). Where mm is the number of rows, and nn is the number of columns. We must iterate over the whole matrix a couple of times.

Space Complexity: O(1)O(1). We can do it in constant extra space, by using the first row/column to track which rows and columns are zeroed out and using boolean values to handle the first row/column.

Written by @ColeB2
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
Do not return anything, modify matrix in-place instead.
# Track our rows and columns.
ROWS, COLS = len(matrix), len(matrix[0])
# iterate first column, if any value is 0, set first_col to True.
# python any method will set first_row to a boolean, based on
# if the condition we provided ever occurs, we can then also
# loop through all the values and check.
first_row = any(matrix[0][c] == 0 for c in range(COLS))
# iterate first row to check for 0's, if any value is a 0, then
# the first column needs to be zeroed out.
first_col = any(matrix[r][0] == 0 for r in range(ROWS))
# Note above: Our first row, will be all the values in
# the row going horizontally, which means we are checking
# the value of each column in row 0, similarly, our first
# column will be all the values in the column going vertically,
# so we check the value of each row in column 0.

# Iterate our matrix, skipping the first row/column
for r in range(1, ROWS):
for c in range(1, COLS):
# found a 0, set the first/row column value to 0
if matrix[r][c] == 0:
matrix[r][0] = 0
matrix[0][c] = 0
# Set the row/columns to zeroes. Again iterate matrix, skipping
# the first row/column
for r in range(1, ROWS):
for c in range(1, COLS):
# if either the first row of any given cell or
# the first column of any given cell is 0, we can
# set the current cell to 0.
if matrix[r][0] == 0 or matrix[0][c] == 0:
matrix[r][c] = 0
# Edge cases, if the first row was 0, set all column values in
# the top row to 0.
if first_row:
for c in range(COLS):
matrix[0][c] = 0
# if first_column contained a 0, set all row values in the left
# column to 0.
if first_col:
for r in range(ROWS):
matrix[r][0] = 0