73. Set Matrix Zeroes
🟧 Medium
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:
A straightforward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant space solution?
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]]
Constraints
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1
Solution
My Solution
func setZeroes(matrix [][]int) {
m := len(matrix)
n := len(matrix[0])
marks := make([]int, m+n)
for i := range marks {
marks[i]=-1
}
for i, row := range matrix {
for j, num := range row {
if num == 0 {
marks[i]=1
marks[m+j]=1
}
}
}
for i, mark := range marks[:m] {
if mark != -1 {
matrix[i] = make([]int,n)
}
}
for i, mark := range marks[m:] {
if mark != -1 {
for _, row := range matrix {
row[i]=0
}
}
}
}
Optimal solution
func setZeroes(matrix [][]int) {
m, n := len(matrix), len(matrix[0])
firstRowZero := false
firstColZero := false
// Step 1: Determine which rows and columns need to be zero
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if matrix[i][j] == 0 {
if i == 0 {
firstRowZero = true
}
if j == 0 {
firstColZero = true
}
matrix[i][0] = 0
matrix[0][j] = 0
}
}
}
// Step 2: Use the markers to set zeroes
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if matrix[i][0] == 0 || matrix[0][j] == 0 {
matrix[i][j] = 0
}
}
}
// Step 3: Handle the first row
if firstRowZero {
for j := 0; j < n; j++ {
matrix[0][j] = 0
}
}
// Step 4: Handle the first column
if firstColZero {
for i := 0; i < m; i++ {
matrix[i][0] = 0
}
}
}

Leetcode: link
Last updated
Was this helpful?