#73 Set Matrix Zeroes
frequently reported atWalmartBloombergMicrosoftMetaAmazonApple
the problem
In plain words
You are given an m × n matrix of integers. For every cell that holds 0 in the original matrix, turn its entire row and its entire column into 0s. Change the matrix in place. Bonus: use only O(1) extra memory.
in matrix = [[1,1,1],[1,0,1],[1,1,1]]
out [[1,0,1],[0,0,0],[1,0,1]]
The 0 in the middle wipes row 1 and column 1.
in matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
out [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
The two zeros in row 0 wipe row 0, column 0 and column 3.
- 1 ≤ m, n ≤ 200
- −2³¹ ≤ matrix[i][j] ≤ 2³¹ − 1
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternIn-place markersMatrix traversal & in-place transforms
You can't zero as you scan: new zeros would look like original ones. Record which rows and columns must go, then write. The record fits inside the matrix: row r's mark in matrix[r][0], column c's in matrix[0][c], because those cells end up 0 anyway.
solutions
From brute force to optimal
Copy the matrix. For each 0 in the copy, zero that row and column in the original.
- Deep-copy the matrix.
- For every 0 found in the copy, set its row and column to 0 in the original.
Each original 0 wipes m + n cells; there can be m·n zeros.
A full copy of the matrix.
class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; int[][] original = new int[m][]; for (int r = 0; r < m; r++) original[r] = matrix[r].clone(); // read zeros from here only for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) if (original[r][c] == 0) { for (int k = 0; k < n; k++) matrix[r][k] = 0; // its whole row for (int k = 0; k < m; k++) matrix[k][c] = 0; // its whole column } }}One pass records which rows and columns hold a 0; a second pass zeroes every cell whose row or column is flagged.
- boolean[] zeroRow(m), zeroCol(n).
- Pass 1: on a 0 at (r, c), flag row r and column c.
- Pass 2: zero (r, c) if zeroRow[r] or zeroCol[c].
Two passes over the matrix.
One boolean per row and per column.
class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; boolean[] zeroRow = new boolean[m], zeroCol = new boolean[n]; for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) if (matrix[r][c] == 0) { zeroRow[r] = true; zeroCol[c] = true; } for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) if (zeroRow[r] || zeroCol[c]) matrix[r][c] = 0; }}Store the flags inside the matrix: matrix[r][0] for row r, matrix[0][c] for column c. Two booleans remember row 0's and column 0's own zeros.
- firstRowZero / firstColZero = does row 0 / column 0 contain a 0?
- For inner cells (r, c ≥ 1) holding 0: matrix[r][0] = 0 and matrix[0][c] = 0.
- For inner cells: zero (r, c) if matrix[r][0] == 0 or matrix[0][c] == 0.
- Last, zero row 0 and/or column 0 if their booleans say so.
Two passes over the matrix plus one pass over row 0 and column 0.
Two booleans; the marks reuse cells that end up 0 anyway.
class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; boolean firstRowZero = false, firstColZero = false; for (int c = 0; c < n; c++) if (matrix[0][c] == 0) firstRowZero = true; for (int r = 0; r < m; r++) if (matrix[r][0] == 0) firstColZero = true; for (int r = 1; r < m; r++) { // phase 1: write the markers for (int c = 1; c < n; c++) { if (matrix[r][c] == 0) { matrix[r][0] = 0; // row r must become zero matrix[0][c] = 0; // column c must become zero } } } for (int r = 1; r < m; r++) { // phase 2: obey the markers for (int c = 1; c < n; c++) { if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0; } } if (firstRowZero) for (int c = 0; c < n; c++) matrix[0][c] = 0; // markers last if (firstColZero) for (int r = 0; r < m; r++) matrix[r][0] = 0; }}Dry run
in the room
How to say it in the interview
talk track
- Say why zeroing on the fly fails: the new zeros are indistinguishable from the original ones.
- Give the O(m + n) flags version first. It's clear and quick to code.
- Then move the flags into row 0 and column 0, and explain why
matrix[0][0]can't serve both, hence two booleans. - Stress the order: inner cells first, row 0 and column 0 last.
traps
- Zeroing row 0 or column 0 before the inner cells have read their marks.
- Using
matrix[0][0]as the flag for both row 0 and column 0: a 0 in either one would wipe the other. - Marking with a sentinel like −1 or
Integer.MIN_VALUE: those are legal cell values here.
what they ask next
Follow-ups
Why is writing a 0 marker into matrix[r][0] never harmful?
It's only written when row r must be wiped, so that cell was going to be 0 anyway. The only information it could hide is column 0's own zeros, which firstColZero saved first.
Can you use one boolean instead of two?
Yes: keep one boolean for column 0 and let matrix[0][0] mark row 0. Then fill from the bottom row up, so row 0 (which holds the column marks) changes last, and set matrix[r][0] from the boolean at the end of each row. Two booleans are easier to get right under pressure.
before you submit
Edge cases to test
- A 0 in row 0 or column 0 (including matrix[0][0]).
- A single row or a single column.
- No zeros at all → the matrix is unchanged.
- Values like Integer.MIN_VALUE: no value is free to use as a special marker.
practise next
Similar problems
- #289Game of LifeMediumin Matrices
- #41First Missing PositiveHardin Arrays & Strings
- #48Rotate ImageMediumin Matrices