# 22. Maximal Square

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

## Solution: (Bruteforce)

**Algorithm:** \
**When we get a square with 1**\
**We expand row, column 1 cell forward**

```cpp
class Solution
{
public:
    int maximalSquare(vector<vector<char>> &matrix)
    {
        int n = matrix.size();
        int m = matrix[0].size();

        int maxSquare = 0;
        for (int i = 0; i < matrix.size(); i++)
        {
            for (int j = 0; j < matrix[0].size(); j++)
            {

                if (matrix[i][j] == '1')
                {
                    bool isSquare = true;
                    int x = i;
                    int y = j;

                    while (isSquare && x < n && y < m)
                    {
                        for (int p = i; p <= x; p++)
                        {
                            for (int q = j; q <= y; q++)
                            {
                                if (matrix[p][q] == '0')
                                {
                                    isSquare = false;
                                    break;
                                }
                            }
                            if (!isSquare)
                            {
                                break;
                            }
                        }

                        if (isSquare)
                        {

                            int square = (x - i) + 1;
                            if (square > maxSquare)
                            {
                                maxSquare = square;
                            }
                            x++;
                            y++;
                        }
                    }
                }
            }
        }
        return maxSquare * maxSquare;
    }
};
```

**Time Complexity: O(m \* n) ^ 2**

## Solution: (DP)

Algorithm:<br>

```cpp
class Solution
{
public:
    int maximalSquare(vector<vector<char>> &matrix)
    {

        int n = matrix.size();
        int m = matrix[0].size();

        vector<vector<int>> v(n + 1, vector<int>(m + 1, 0));
        int maxSquare = 0;

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (matrix[i - 1][j - 1] == '1')
                {
                    int min1 = min(v[i][j - 1], v[i - 1][j]);
                    int mn = min(min1, v[i - 1][j - 1]);

                    if (mn == 0)
                    {
                        v[i][j] = 1;
                    }
                    else
                    {
                        v[i][j] = 1 + mn;
                    }
                    
                    if (v[i][j] > maxSquare)
                    {
                        maxSquare = v[i][j];
                    }
                }
                else
                {
                    v[i][j] = 0;
                }
            }
        }
        
        return maxSquare * maxSquare;
    }
};
```

**Time Complexity: O(m \* n)** \
**Space Complexity: O(m+n)**