Start learning free

LESSON 292 OF 501 · MATRIX

Set Matrix Zeroes in Python

Practice O(m*n)

Given an m x n matrix of integers matrix, wherever an element is 0, set its entire row and its entire column to 0.

Do it in place: change matrix itself and return nothing.

A matrix is a list of rows, and each row is a list of integers. Rows are numbered from 0, top to bottom, and columns from 0, left to right. Only the zeros that are in matrix at the start count: a cell that becomes 0 doesn't clear its own row and column.

 

Example 1:

Input: matrix = [
  [1, 1, 1],
  [1, 0, 1],
  [1, 1, 1]
]
Output: [
  [1, 0, 1],
  [0, 0, 0],
  [1, 0, 1]
]
Explanation: The only 0 is in row 1 and column 1, so the whole middle row and the whole middle column become 0.

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]
]
Explanation: Both zeros are in row 0, in columns 0 and 3. Row 0 becomes all zeros, and so do columns 0 and 3.

Example 3:

Input: matrix = [
  [0, 2, 3, 4],
  [5, 0, 7, 8],
  [9, 10, 11, 12]
]
Output: [
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 11, 12]
]
Explanation: The zeros in row 0, column 0 and in row 1, column 1 clear rows 0 and 1 and columns 0 and 1. The cells that only became 0 clear nothing more, so 11 and 12 stay.

 

Constraints:

  • m is the number of rows and n the number of columns: 1 <= m, n <= 500
  • Every row has the same number of values, n.
  • -231 <= matrix[i][j] <= 231 - 1

Note:

Your algorithm should run in O(m * n) time and use O(m + n) extra space.

Follow-up: can you do it with O(1) extra space? The first row and the first column of matrix can hold the marks for the other rows and columns.

STEP 1 OF 9
    Ctrl + Enter to check

    Set Matrix Zeroes in Python

    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free