LeetCode 73 · Medium · Math & Geometry

Set Matrix Zeroes

Wherever the matrix holds a 0, turn that cell's whole row and whole column into zeros. Change the matrix in place, using only a constant amount of extra memory.

O(m · n)time
O(1)space
first row + columndouble as markers

rows separated by ; and values by commas · 1–6 rows of 1–6 values, all rows the same length · integers −99 to 999

matrix ↓ in row 0 marks a column to clear · → in column 0 marks a row · rowZero remembers row 0 itself

public void setZeroes(int[][] matrix) { int rows = matrix.length; int cols = matrix[0].length; boolean rowZero = false; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { if (matrix[r][c] == 0) { matrix[0][c] = 0; if (r > 0) { matrix[r][0] = 0; } else { rowZero = true; } } } } for (int r = 1; r < rows; r++) { for (int c = 1; c < cols; c++) { if (matrix[0][c] == 0 || matrix[r][0] == 0) { matrix[r][c] = 0; } } } if (matrix[0][0] == 0) { for (int r = 0; r < rows; r++) { matrix[r][0] = 0; } } if (rowZero) { for (int c = 0; c < cols; c++) { matrix[0][c] = 0; } }}
r, c
—
rowZero
false
rows marked
—
columns marked
—

Why it works

  1. Zeroing as you scan is wrong: the new zeros would wipe out more rows and columns. The simple fix stores two sets, the zero rows and zero columns, then clears them: O(m · n) time but O(m + n) space.
  2. The matrix can hold its own markers: row 0 has one cell per column and column 0 one cell per row. Writing a 0 into matrix[0][c] says "clear column c"; into matrix[r][0], "clear row r". Those cells are going to be zero anyway, so nothing is lost.
  3. The corner clash: matrix[0][0] cannot mark both row 0 and column 0. It marks column 0, and the flag rowZero records whether row 0 itself had a zero. That is the O(1) extra space.
  4. Order matters (pitfall): clear the inner cells first, reading the markers, then column 0, then row 0. Clearing row 0 or column 0 earlier would erase markers still needed, and every column or row would look marked.
  5. Cost: two passes over the matrix plus one sweep of the first row and column: O(m · n) time, two loop variables and one flag of space.