# 0221. Maximal Square

https://leetcode.com/problems/maximal-square

## Description

Given an `m x n` binary `matrix` filled with `0`'s and `1`'s, _find the largest square containing only_ `1`'s _and return its area_.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/11/26/max1grid.jpg)

```
**Input:** matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
**Output:** 4
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/11/26/max2grid.jpg)

```
**Input:** matrix = [["0","1"],["1","0"]]
**Output:** 1
```

**Example 3:**

```
**Input:** matrix = [["0"]]
**Output:** 0
```

**Constraints:**

* `m == matrix.length`
* `n == matrix[i].length`
* `1 <= m, n <= 300`
* `matrix[i][j]` is `'0'` or `'1'`.

## ac1: DP

Typical DP that makes use of top/left/top-left.

```java
class Solution {
    public int maximalSquare(char[][] matrix) {
        int max = 0;

        for (int r = 0; r < matrix.length; r++) {
            for (int c = 0; c < matrix[0].length; c++) {
                if (matrix[r][c] == '0') continue;
                if (r - 1 >= 0 && c - 1 >= 0) {
                    int min = Math.min(Math.min(matrix[r-1][c-1] - '0', matrix[r-1][c] - '0'), matrix[r][c-1] - '0');
                    matrix[r][c] = (char)('0' + min + 1);
                }

                max = Math.max(max, matrix[r][c] - '0');
            }
        }

        return max * max;
    }
}
```
