Start learning free

LESSON 341 OF 678 · MATRIX

Set Matrix Zeroes

Practice O(m*n)

You get a grid of integers, matrix, with m rows and n columns.

Wherever a cell is 0, set its whole row and its whole column to 0. Change matrix in place and return nothing.

Only the zeros that are there at the start count. A cell you turn into 0 doesn't clear anything more.

The grid is an array of rows. Each row is an array of integers. Rows are counted from 0 at the top, columns from 0 at the left.

 

Example 1:

Input: matrix = [
  [4, 0, 6],
  [7, 8, 9]
]
Output: [
  [0, 0, 0],
  [7, 0, 9]
]
Explanation: The 0 is in row 0, column 1.
It clears row 0 and column 1.
The 7 and the 9 stay.

Example 2:

Input: matrix = [
  [2, 5, 8],
  [0, 3, 1],
  [6, 4, 0]
]
Output: [
  [0, 5, 0],
  [0, 0, 0],
  [0, 0, 0]
]
Explanation: Two cells are 0 at the start.
The 0 in row 1, column 0 clears row 1 and column 0.
The 0 in row 2, column 2 clears row 2 and column 2.
The 5 stays. Row 0 and column 1 had no 0 at the start.
The new zeros in row 0 don't count.

Example 3:

Input: matrix = [
  [7, 2, 9, 3]
]
Output: [
  [7, 2, 9, 3]
]
Explanation: There is no 0. Nothing changes.

 

Constraints:

  • 1 to 500 rows.
  • 1 to 500 columns.
  • All rows have the same length.
  • Each value fits in a 32-bit signed integer: -231 to 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