Problem overview
The method setZeroes(matrix) receives an m x n matrix, an array of m rows with n integers each. Wherever a cell holds 0, its whole row and whole column must become 0. The change happens in place and the method returns nothing. Only the zeros present at the start count: a cell that becomes 0 during the process doesn't clear its own row and column.
For [[1, 1, 1], [1, 0, 1], [1, 1, 1]] the only zero is at row 1, column 1, so the middle row and middle column become zeros: [[1, 0, 1], [0, 0, 0], [1, 0, 1]]. For [[0, 2, 3, 4], [5, 0, 7, 8], [9, 10, 11, 12]] the zeros clear rows 0 and 1 and columns 0 and 1, and the result is [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 11, 12]]. The 11 and 12 survive because no original zero sits in their row or column.
Approach: remember now, clear later
The tempting solution scans the matrix and, on finding a zero, zeroes its row and column immediately. That is wrong. The new zeros look exactly like original ones, so the scan reaches them later and clears more rows and columns than it should. On the first example, that eager version returns [[1, 0, 0], [0, 0, 0], [0, 0, 0]] instead of the expected matrix, and on the second example it turns the entire matrix into zeros.
The fix is to split the work into two passes:
- Read pass: look at every cell and write down which rows and columns contain a zero. Nothing in the matrix changes yet.
- Write pass: set a cell to 0 whenever its row or its column was marked.
Two boolean arrays hold the marks: zeroRow[i] says whether row i has a zero, and zeroCol[j] says the same for column j. Several zeros in the same row just mark it again, which is harmless. Both passes visit every cell once, so the time is O(m * n), and the marks use O(m + n) extra space, which is what the statement allows. The follow-up in the statement reaches O(1) extra space by keeping the marks in the matrix's own first row and first column. This lesson uses the simpler arrays.
Step by step
- Store the dimensions:
mismatrix.lengthandnismatrix[0].length. Every row has the same length, so the first row gives the column count. - Create the mark arrays,
zeroRowwithmentries andzeroColwithnentries, allfalse. They areconstbecause the arrays themselves are never replaced, only their entries change. - Loop over the rows and, inside, over the columns. Together the two loops reach every cell once. This first pass only reads the matrix.
- Test each cell with
matrix[i][j] === 0. - Mark its row and column by setting
zeroRow[i]andzeroCol[j]totrue. - Start the second pass with the same pair of nested loops. Every zero is recorded now, so changing cells can't lose information.
- Clear a cell when
zeroRow[i] || zeroCol[j]is true by settingmatrix[i][j] = 0.
The solution in JavaScript
class Solution {
setZeroes(matrix) {
const m = matrix.length;
const n = matrix[0].length;
const zeroRow = new Array(m).fill(false);
const zeroCol = new Array(n).fill(false);
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 0) {
zeroRow[i] = true;
zeroCol[j] = true;
}
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (zeroRow[i] || zeroCol[j]) {
matrix[i][j] = 0;
}
}
}
}
}
Some JavaScript details worth knowing:
new Array(m).fill(false).new Array(3)alone creates an array with three empty slots, printed as[ <3 empty items> ]. Callingfill(false)gives it three realfalsevalues. The marks are then safe to read.===for the zero test. It compares a number with a number and doesn't convert types. The==operator would also treat values such as""andfalseas equal to 0, which can't occur in this problem but is a habit worth avoiding.||short-circuits. IfzeroRow[i]is alreadytrue,zeroCol[j]isn't looked at. The result is a plain boolean here because both operands are booleans.- In place means through the rows. Each
matrix[i]is an array object, so assigningmatrix[i][j] = 0changes the caller's matrix. The method has noreturn, so a call givesundefined. - Large values are fine. JavaScript numbers are doubles, which hold every 32-bit integer exactly, including
-2147483648. For[[-2147483648, 0], [7, 8]]the result is[[0, 0], [7, 0]]. The 7 survives because neither its row nor its column (column 0) holds an original zero.
Complexity
Time: O(m * n). Each of the two passes visits every cell once, doing constant work per cell.
Space: O(m + n). The two boolean arrays hold one entry per row and one per column. No copy of the matrix is made.
Edge cases and common mistakes
- Clearing while scanning. Setting a row and column to 0 the moment a zero is seen makes the new zeros spread. For
[[0, 2, 3, 4], [5, 0, 7, 8], [9, 10, 11, 12]]the eager version returns all zeros, while the expected answer keeps 11 and 12. - No zeros.
[[1, 2], [3, 4]]is returned unchanged, since no mark is ever set. - One row or one column.
[[1, 2, 3]]has no zero and stays the same.[[1], [0], [3]]becomes[[0], [0], [0]], because the zero's column is the whole matrix. - A matrix holding a single 0.
[[0]]stays[[0]]. - Mixing up the dimensions.
zeroRowneedsmentries (rows) andzeroColneedsn(columns). Swapping them breaks on non-square matrices such as the 3 by 4 examples. - Returning something. The tests look at
matrixitself, so a new matrix you build and return is ignored.
Testing
[[1, 1, 1], [1, 0, 1], [1, 1, 1]]gives[[1, 0, 1], [0, 0, 0], [1, 0, 1]].[[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]gives[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]].[[0, 2, 3, 4], [5, 0, 7, 8], [9, 10, 11, 12]]gives[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 11, 12]].[[1], [0], [3]]gives[[0], [0], [0]].[[1, 2], [3, 4]]gives[[1, 2], [3, 4]].
