Repository navigation
168 — Set Matrix Zeroes
LeetCode 73 · Medium. Given an m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Imagine a spreadsheet where finding a single 0 in a cell means "condemn this entire row and this entire column." You can't zero things out the instant you spot a 0, though — if you did, you'd start turning other cells to 0 before you've finished scanning the original matrix, and then those newly-created zeroes would incorrectly condemn even more rows and columns that were never supposed to be touched. So the safe approach is always two passes: first, figure out which rows and columns are condemned by scanning the untouched matrix, and only then go back and actually zero them out.
original: which rows/cols get condemned: result:
1 1 1 row 1 has a 0 -> condemn row 1 1 0 1
1 0 1 col 1 has a 0 -> condemn col 1 0 0 0
1 1 1 1 0 1
"Set the entire row and column to zero" based on cells discovered during a scan of that same matrix is the two-pass grid signal: whenever acting on a discovery immediately would corrupt data you still need to read, split the work into a "record what needs to happen" pass and an "apply it" pass over the same grid.
Scan the whole matrix once to record every row and column that contains a 0 into two sets, then scan it again and zero out any cell whose row or column was recorded.
func setZeroesBruteForce(_ matrix: inout [[Int]]) {
let rows = matrix.count
let cols = matrix[0].count
var zeroRows = Set<Int>()
var zeroCols = Set<Int>()
for r in 0..<rows {
for c in 0..<cols {
if matrix[r][c] == 0 {
zeroRows.insert(r)
zeroCols.insert(c)
}
}
}
for r in 0..<rows {
for c in 0..<cols {
if zeroRows.contains(r) || zeroCols.contains(c) {
matrix[r][c] = 0
}
}
}
}
// smoke test
var grid1: [[Int]] = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
setZeroesBruteForce(&grid1)
print(grid1)
// [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
var grid2: [[Int]] = [
[0, 1, 2, 0],
[3, 4, 5, 2],
[1, 3, 1, 5]
]
setZeroesBruteForce(&grid2)
print(grid2)
// [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]Big-O: O(m * n) time — two full passes over the grid. O(m + n) extra space for the two sets.
Instead of two separate sets, use the matrix's own first row and first column as the marker storage — if matrix[r][c] is 0, mark it by zeroing matrix[r][0] and matrix[0][c]. Since the first row and first column would then be corrupted by their own "am I condemned" markers, track whether they themselves originally contained a 0 in two standalone booleans before touching anything.
func setZeroes(_ matrix: inout [[Int]]) {
let rows = matrix.count
let cols = matrix[0].count
var firstRowHasZero = false
var firstColHasZero = false
for c in 0..<cols where matrix[0][c] == 0 { firstRowHasZero = true }
for r in 0..<rows where matrix[r][0] == 0 { firstColHasZero = true }
// use row 0 / col 0 as marker storage for every other row/column
for r in 1..<rows {
for c in 1..<cols {
if matrix[r][c] == 0 {
matrix[r][0] = 0
matrix[0][c] = 0
}
}
}
// zero out every cell whose row-marker or column-marker was set
for r in 1..<rows {
for c in 1..<cols {
if matrix[r][0] == 0 || matrix[0][c] == 0 {
matrix[r][c] = 0
}
}
}
// finally, handle row 0 and column 0 themselves using the flags recorded up front
if firstRowHasZero {
for c in 0..<cols { matrix[0][c] = 0 }
}
if firstColHasZero {
for r in 0..<rows { matrix[r][0] = 0 }
}
}
// smoke test — same cases as the brute force
var grid3: [[Int]] = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
setZeroes(&grid3)
print(grid3)
// [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
var grid4: [[Int]] = [
[0, 1, 2, 0],
[3, 4, 5, 2],
[1, 3, 1, 5]
]
setZeroes(&grid4)
print(grid4)
// [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]Big-O: O(m * n) time — still a small constant number of passes over the grid. O(1) extra space — only two boolean flags, no separate sets.
The two sets in the brute force exist purely to remember which rows/columns are condemned until the second pass can act on that memory — but the matrix already has a place to remember that: the first row and first column, which are themselves rows/columns of the same grid. The only wrinkle is that row 0 and column 0 need to record markers for every other row and column while also being condemned-or-not themselves, so their own original zero-ness has to be captured in two standalone flags before any marker-writing begins. Reusing existing storage instead of allocating new storage is exactly what turns O(m + n) space into O(1).
- Arrays and Strings — the 2-D array being scanned and mutated in place across two passes.
- Matrix Traversal — the two-pass grid scan (record, then apply), a variation on this chapter's general "walk every cell" traversal shape.
Set Matrix Zeroes is condemning a spreadsheet's rows and columns — mark which ones are condemned first, using the grid's own first row and column as your notepad, then sweep through and zero them out.
- Why can't the brute force zero out cells as soon as a
0is found during the very first scan, instead of collectingzeroRows/zeroColsand doing a second pass? - Why must
firstRowHasZeroandfirstColHasZerobe computed before the marker-writing loop runs, rather than checked later by just looking atmatrix[0][0]? - The marker-writing and marker-reading loops both start at
r = 1andc = 1, skipping row 0 and column 0 entirely. Why would including row 0 or column 0 in those loops corrupt the markers for other rows/columns? - Trace through
grid4above and confirm thatmatrix[0][0]ends up0for the right reason — is it because row 0 originally had a zero, because column 0 originally had a zero, or both?