# Set Matrix Zeroes

## Problem

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm).

**Example 1:**

```
Input:

[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]

Output:

[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]
```

**Example 2:**

```
Input:

[
  [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]
]
```

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

## Analysis

O(mn)的空间解法最直接暴力，就是开辟和输入matrix同等大小的matrix，用来存储新的matrix；

O(m + n)的空间复杂度则是一个提升，考虑到问题的本质其实是对于为0的元素，其对应下标(i, j)对应的行和列需要被记录，因此分别使用 m, n空间记录那些行和列中有0；

O(1)的空间复杂度则需要思考如何利用matrix本身来存储某行某列有0元素的情况，这里就是想到了使用首行`matrix[0][j]`和首列`matrix[i][0]`作为存储该行i 或者该列j 是否应该设为0的状态的空间，同时安排额外两个变量记录首行和首列本身是否应该设为全0.

## Code

```java
class Solution {
    public void setZeroes(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return;

        int m = matrix.length;
        int n = matrix[0].length;

        boolean firstRowZero = false;
        boolean firstColZero = false;

        //check if first row needs to be changed to zero
        for(int j = 0; j < n; j++) {
            if(matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }

        //check if first col needs to be changed to zero
        for(int i = 0; i < m; i++) {
            if(matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }

        //mark the row col which have zero in first row and col
        for(int i = 1; i < m ;i++) {
            for(int j = 1; j < n; j++) {
                if(matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        //fill in the zeroes
        for(int i = 1; i < m ;i++) {
            for(int j = 1; j < n; j++) {
                if(matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
            }
        }

        //update first row
        if(firstRowZero) {
            for(int j = 0; j < n; j++)
                matrix[0][j] = 0;
        }

        //update first col
        if(firstColZero) {
            for(int i = 0; i < m; i++)
                matrix[i][0] = 0;
        }
    }
}
```


---

# 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://aaronice.gitbook.io/lintcode/matrix/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.