## Algorithm

Problem Name: 221. 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:

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

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

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int test_square(char **matrix, int row, int col, int k) {
int x;
for (x = 0; x <= k; x ++) {
if (matrix[row + x][col + k] == '0' ||
matrix[row + k][col + x] == '0') return 0;
}
return 1;
}
int maximalSquare(char** matrix, int matrixRowSize, int matrixColSize) {
int max = 0;
int i, j, k;
for (i = 0; i < matrixRowSize; i ++) {
for (j = 0; j < matrixColSize; j ++) {
k = 0;
while (i + k < matrixRowSize &&
j + k < matrixColSize &&
test_square(matrix, i, j, k)) {
k ++;
}
max = max < k ? k : max;
}
}
return max * max;
}
``````
Copy The Code &

Input

cmd
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

Output

cmd
4

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int maximalSquare(vector>& matrix) {
if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
int maxSquare = 0;
for(int i = 0; i < matrix.size(); i++)
for(int j = 0; j < matrix[0].size(); j++)
if(matrix[i][j] != '0') maxSquare = max(maxSquare, findSquare(matrix, i, j));
return maxSquare;
}

int findSquare(vector>& matrix, int r, int c){
int row = r - 1;
int col = c - 1;
while(row >= 0 && col >= 0 && matrix[r][col] == '1' && matrix[row][c] == '1'){
int i = row;
int j = col;
while(i < r && matrix[i][col] == '1') i++;
while(j < c && matrix[row][j] == '1') j++;
if(i != r || j != c) break;
row--;
col--;
}
return pow(r - row, 2);
}
};
``````
Copy The Code &

Input

cmd
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

Output

cmd
4

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const maximalSquare = function(matrix) {
const rows = matrix.length
const cols = rows > 0 ? matrix[0].length : 0
const dp = Array.from(new Array(rows + 1), el => new Array(cols + 1).fill(0))
let maxLen = 0
for(let i = 1; i <= rows; i++) {
for(let j = 1; j <= cols; j++) {
if(matrix[i - 1][j - 1] === '1') {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
maxLen = Math.max(maxLen, dp[i][j])
}
}
}

return maxLen * maxLen
};
``````
Copy The Code &

Input

cmd
matrix = [["0","1"],["1","0"]]

Output

cmd
1

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
res, count = 0, 0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
matrix[i][j] = int(matrix[i][j])
if matrix[i][j] != 0:
count = 1
if j>0 and int(matrix[i][j-1]) != 0: matrix[i][j] += int(matrix[i][j-1])
if i-1>=0 and int(matrix[i-1][j]) != 0:
k, curr = i-1, []
while k>=0 and k>=i-matrix[i][j]+1 and int(matrix[k][j]) != 0:
if matrix[k][j]>= count+1:
curr.append(matrix[k][j])
if min(curr)>= count+1: count += 1
else: break
k -= 1
res = max(res, count**2)
return res
``````
Copy The Code &

Input

cmd
matrix = [["0","1"],["1","0"]]

Output

cmd
1

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0221_MaximalSquare
{
public int MaximalSquare(char[][] matrix)
{
var row = matrix.Length;
if (row == 0) return 0;
var col = matrix[0].Length;
if (col == 0) return 0;

var dp = new int[col + 1];
int prev = 0, max = 0;
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
{
var temp = dp[j + 1];
if (matrix[i][j] == '1')
{
dp[j + 1] = Math.Min(Math.Min(dp[j], prev), dp[j + 1]) + 1;
max = Math.Max(max, dp[j + 1]);
}
else
dp[j + 1] = 0;

prev = temp;
}

return max * max;
}
}
}
``````
Copy The Code &

Input

cmd
matrix = [["0"]]