Skip to main content

73. Set Matrix Zeroes

medium

Zero out the entire row and column for every 0 in the matrix, in-place. The trick: use the first row and column themselves as bookkeeping flags to avoid extra space.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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. Follow up: could you devise a constant space solution?

Constraints

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

Examples

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

Example 3

Input
matrix = [[1]]
Output
[[1]]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

An O(m + n) extra-space solution uses two sets to track which rows and columns need zeroing. Can you do better?

Hint 2

Reuse the first row and first column as your row-flag and column-flag arrays. But you need a separate flag for whether the first row or first column themselves originally contained a zero.

Hint 3

Two-pass solution: pass 1 records flags into row 0 and column 0; pass 2 reads those flags and zeroes everything except row 0 and column 0. Then handle row 0 and column 0 last using the saved boolean flags.

Solution approach

Reveal approach

Use the matrix's own first row and first column as flags. Step 1: scan the entire matrix; if you find matrix[i][j] == 0, set matrix[i][0] = 0 and matrix[0][j] = 0. But you also need two booleans firstRowZero and firstColZero to remember whether the first row or first column themselves contained any zero originally, because those flag cells will collide with real data. Step 2: for every cell (i, j) with i > 0 and j > 0, set matrix[i][j] = 0 if matrix[i][0] == 0 or matrix[0][j] == 0. Step 3: if firstRowZero, zero the entire first row. Step 4: if firstColZero, zero the entire first column. This achieves O(1) extra space while staying O(m*n) time.

Complexity

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

Related patterns

  • in-place
  • matrix

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple
  • Meta
  • Google

Practice these live with InterviewChamp.AI

Drill Set Matrix Zeroes and Arrays problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →