# Maximal Square

`Dynamic Programming`

## Question

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

**Example**

For example, given the following matrix:

```
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
```

Return 4.

**Tags**

Dynamic Programming Airbnb Facebook

**Related Problems**

Hard Maximal Rectangle

## Analysis

考虑以`f[i][j]`为右下角顶点可以拓展的正方形边长，那么可以由`f[i-1][j]`，`f[i][j-1]`，`f[i-1][j-1]`三者的最小值决定`f[i][j]`的最长边长。

> 当我们判断以某个点为正方形右下角时最大的正方形时，那它的上方，左方和左上方三个点也一定是某个正方形的右下角，否则该点为右下角的正方形最大就是它自己了。这是定性的判断，那具体的最大正方形边长呢？我们知道，该点为右下角的正方形的最大边长，最多比它的上方，左方和左上方为右下角的正方形的边长多1，最好的情况是是它的上方，左方和左上方为右下角的正方形的大小都一样的，这样加上该点就可以构成一个更大的正方形。但如果它的上方，左方和左上方为右下角的正方形的大小不一样，合起来就会缺了某个角落，这时候只能取那三个正方形中最小的正方形的边长加1了。假设`dp[i][j]`表示以i,j为右下角的正方形的最大边长，则有
>
> ```
> dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
> ```
>
> 当然，如果这个点在原矩阵中本身就是0的话，那`dp[i][j]`肯定就是0了。

时间`O(mn)`， 空间`O(mn)`

**DP四要素**

* 状态 State
  * `f[i][j]` 表示以i和j作为正方形右下角可以拓展的最大边长
* 方程 Function
  * if `matrix[i][j] == 1`
    * `f[i][j] = min(f[i - 1][j], f[i][j-1], f[i-1][j-1]) + 1;`
  * if `matrix[i][j] == 0`
    * `f[i][j] = 0`
* 初始化 Intialization
  * `f[i][0] = matrix[i][0];`
  * `f[0][j] = matrix[0][j];`
* 答案 Answer
  * `max{f[i][j]}`

**可以使用二维滚动数组优化:**

1. 状态 State
   * `f[i][j]` 表示以i和j作为正方形右下角可以拓展的最大边长
2. 方程 Function
   * `if matrix[i][j] == 1`
     * `f[i%2][j] = min(f[(i - 1)%2][j], f[i%2][j-1], f[(i-1)%2][j-1]) + 1;`
   * `if matrix[i][j] == 0`
   * `f[i%2][j] = 0`
3. 初始化 Intialization
   * `f[i%2][0] = matrix[i][0];`
   * `f[0][j] = matrix[0][j];`
4. 答案 Answer
   * `max{f[i%2][j]}`

## Solution

### Standard Dynamic Programming

```java
public class Solution {
    /**
     * @param matrix: a matrix of 0 and 1
     * @return: an integer
     */
    public int maxSquare(int[][] matrix) {
        if (matrix.length == 0) return 0;

        int m = matrix.length, n = matrix[0].length;
        int max = 0;
        int[][] dp = new int[m][n];

        // 第一列赋值
        for (int i = 0; i < m; i++) {
            dp[i][0] = matrix[i][0];
            max = Math.max(max, dp[i][0]);
        }

        // 第一行赋值
        for (int i = 0; i < n; i++) {
            dp[0][i] = matrix[0][i];
            max = Math.max(max, dp[0][i]);
        }

        // 递推
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = matrix[i][j] == 1 ? Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1 : 0;

                max = Math.max(max, dp[i][j]);
            }
        }
        return max * max;
    }
}
```

### LeetCode version (`char[][]` as input) - (12ms 30.09%)

```java
class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;

        int[][] dp = new int[m][n];
        int maxSqLen = 0;
        for (int i = 0; i < m; i++) {
            dp[i][0] = matrix[i][0] == '1' ? 1 : 0;
            maxSqLen = Math.max(dp[i][0], maxSqLen);
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = matrix[0][j] == '1' ? 1 : 0;
            maxSqLen = Math.max(dp[0][j], maxSqLen);
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    maxSqLen = Math.max(dp[i][j], maxSqLen);
                } 
            }
        }
        return maxSqLen * maxSqLen;
    }
}
```

### A smart way to bypass initialization, use `m + 1`, `n + 1` as `dp[][]` dimension:

(notice `matrix[i-1][j-1]` is used for determining `dp[i][j]`) - `O(mn)` time, `O(mn)` space - (13 ms, faster than 23.53%)

```java
public class Solution {
    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
        int[][] dp = new int[rows + 1][cols + 1];
        int maxsqlen = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (matrix[i-1][j-1] == '1'){
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                    maxsqlen = Math.max(maxsqlen, dp[i][j]);
                }
            }
        }
        return maxsqlen * maxsqlen;
    }
}
```

### Space optimized DP - O(mn) time, O(n) space

```java
public class Solution {
    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
        int[] dp = new int[cols + 1];
        int maxsqlen = 0, prev = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                int temp = dp[j];
                if (matrix[i - 1][j - 1] == '1') {
                    dp[j] = Math.min(Math.min(dp[j - 1], prev), dp[j]) + 1;
                    maxsqlen = Math.max(maxsqlen, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = temp;
            }
        }
        return maxsqlen * maxsqlen;
    }
}
```

## Reference

* [segmentfault: Maximal Square 最大正方形](https://segmentfault.com/a/1190000003709497)
* [LeetCode - Maximal Square](https://leetcode.com/articles/maximal-square/)


---

# 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/dynamic_programming/maximal-square.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.