AlgoViz
HomeArrays & Hashing

Set Matrix Zeroes

Medium

Use the first row and column as the marker board

Problem

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0. You must do it in place.

In simple words

First note which rows and columns contain a zero, then blank them all out.

The idea

Zeroing cells as you find them corrupts the data you have not read yet, so first record which rows and columns must be cleared. Storing those flags in the matrix's own first row and column gets it done in O(1) extra space, provided you handle that first row and column last.

The trick

  • Two passes: mark, then apply. Never mark and apply together.
  • Track separately whether the first row and first column themselves contained a zero.
  • Apply from the inside outwards so the markers stay readable.
1
1
1
1
0
1
1
1
1
zero at(1,1)

Step 1 of 3. Found a 0 at (1,1). Use row/column heads as bookmarks instead of extra arrays. zero at (1,1).

1/3
Optimal
timeO(rows·cols)spaceO(1)

No extra arrays.

1for r, c in every cell:2  if M[r][c] == 0: M[r][0] = M[0][c] = 03for r, c in every cell except row 0 and column 0:4  if M[r][0] == 0 or M[0][c] == 0: M[r][c] = 05if firstRowHadZero: zero every cell of row 06if firstColHadZero: zero every cell of column 0

Input

grid
3 × 3

Memory

at
row 1, column 1
cells marked
1
zero at
(1,1)

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

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 0's whole row and column go to 0.

Example 2

Input:
matrix = [[0,1],[1,1]]
Output:
[[0, 0], [0, 1]]
Explanation:
The corner 0 clears its row and column.

Example 3

Input:
matrix = [[1,2],[3,4]]
Output:
[[1, 2], [3, 4]]
Explanation:
No zeros → nothing changes.

Constraints

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

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.