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 .
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?
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
}
}
}
