# 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](https://en.wikipedia.org/wiki/In-place_algorithm).

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](https://assets.leetcode.com/uploads/2020/08/17/mat1.jpg)

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

```go
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

```go
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](https://600345290-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FrSK2xH3txU3tYyDsT8mQ%2Fuploads%2Fgit-blob-803ab8c18990db7ffa3641e01e2ddfb0e7ced152%2F73.png?alt=media)

Leetcode: [link](https://leetcode.com/problems/set-matrix-zeroes/description)