# 73. Set Matrix Zeroes

## LeetCode [73. Set Matrix Zeroes](https://leetcode-cn.com/problems/set-matrix-zeroes/)

### Description

Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.

Follow up:

* A straight forward 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?

### Tags

Array

### Solution

直接的解法（见解法2）是用两个分别与行和列等长的布尔数组标记对应行列是否存在0，再遍历一遍所有元素，检查其行列号在两数组的对应位置上是否已被标记，如果至少有一个被标记则修改该位置元素为0。

进阶的解法（见解法1）是采用第一行和第一列作为这两个数组，但考虑到二者可能自身就包含0，所以先使用两个布尔变量来记录二者是否含0。从下标(1, 1)开始做与上个解法相同的事。最后根据两个变量来判断是否要把第一行或第一列设置全0。

A simple solution is using 2 boolean arrays whose length equal to the rows and columns of the matrix respectively to mark the presence or absence of 0 in the corresponding row or column. Then traverse all elements and check if its row/col number is marked in the corresponding position of the two arrays. Set the current element to 0 if one of both positions is marked.

An advanced solution is to use the first row and column to substitute 2 arrays to save space. However, each of them might contains 0. Therefore, 2 boolean variables are used to record if the first row and column contain 0 before we perform the same solution.

### Complexity

#### Solution 1:

* Time complexity: $$O(mn)$$
* Space complexity: $$O(1)$$

#### Solution 2:

* Time complexity: $$O(mn)$$
* Space complexity: $$O(m+n)$$

### Code

#### Solution 1: Space complexity O(1) (2 variables)

```go
// Solution 1: Space complexity O(1) (2 variables)
func setZeroes(matrix [][]int) {
	var row0, col0 bool
	for _, l := range matrix {
		if l[0] == 0 {
			col0 = true
			break
		}
	}
	for _, v := range matrix[0] {
		if v == 0 {
			row0 = true
			break
		}
	}
	for i := 1; i < len(matrix); i++ {
		for j := 1; j < len(matrix[0]); j++ {
			if matrix[i][j] == 0 {
				matrix[i][0] = 0
				matrix[0][j] = 0
			}
		}
	}
	for i := 1; i < len(matrix); i++ {
		for j := 1; j < len(matrix[0]); j++ {
			if matrix[i][0] == 0 || matrix[0][j] == 0 {
				matrix[i][j] = 0
			}
		}
	}
	if col0 {
		for i := range matrix {
			matrix[i][0] = 0
		}
	}
	if row0 {
		for j := range matrix[0] {
			matrix[0][j] = 0
		}
	}
}
```

#### Solution 2: Space complexity O(m+n) (2 arrays)

```go
func setZeroes(matrix [][]int) {
	rows, cols := make([]bool, len(matrix)), make([]bool, len(matrix[0]))
	for i, l := range matrix {
		for j, v := range l {
			if v == 0 {
				rows[i], cols[j] = true, true
			}
		}
	}
	for i, l := range matrix {
		for j := range l {
			if rows[i] || cols[j] {
				l[j] = 0
			}
		}
	}
}
```

## Reference

1. [矩阵置零](https://leetcode-cn.com/problems/set-matrix-zeroes/solution/ju-zhen-zhi-ling-by-leetcode-solution-9ll7/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/73.-set-matrix-zeroes.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.