> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0221-maximal-square.md).

# 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;
    }
}
```