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

matrix

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

result

Leetcode: link