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.

&nbsp;
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


&nbsp;
Constraints:


	m == matrix.length
	n == matrix[i].length
	1 &lt;= m, n &lt;= 300
	matrix[i][j] is '0' or '1'.


class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[-1])   
        dp = [[0] * n for _ in range(m)]     
        max_area = 0
        for i in range(m):
            for j in range(n): 
                if i - 1 < 0 or j - 1 < 0:
                    if matrix[i][j] == '1': dp[i][j] = 1
                else:
                    if matrix[i][j] == '1':
                        dp[i][j] = 1 + min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])
                max_area = max(max_area, dp[i][j] ** 2)
        return max_area
class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];

        int max = 0;

        for (int i = 0; i < m; i++) {
            dp[i][0] = matrix[i][0] - 48;
            if (matrix[i][0] == '1') max = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = matrix[0][i] - 48;
            if (matrix[0][i] == '1') max = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                    if (dp[i][j] > max) {
                        max = dp[i][j];
                    }
                }
            }
        }

        return max * max;
    }
}
class Solution {
public:
    
    int dp[305][305];
    int ans;
    
    int getMax(vector<vector<char>>& mat, int i, int j){
        int n=mat.size(), m=mat[0].size();
        if(i>=n || j>=m) return 0;
        if(dp[i][j] != -1) return dp[i][j];
        
		// getting min of the perfect squares formed by left adjacent, right adjacent, cross adjacent 
		// +1 for including current
        dp[i][j] = min({getMax(mat, i, j+1), getMax(mat, i+1, j), getMax(mat, i+1, j+1)}) + 1;
		// There are no perfect squares if mat[i][j] is zero
        if(mat[i][j] == '0') dp[i][j] = 0;
		
		// final ans = max(ans, current_max);
        ans = max(ans, dp[i][j]);
		
        return dp[i][j];
    }
    
    int maximalSquare(vector<vector<char>>& matrix) {
        memset(dp, -1, sizeof(dp));
        ans = 0;
        getMax(matrix, 0, 0);
        return ans*ans;
    }
};
var maximalSquare = function(matrix) {
    let max = 0;
    const height = matrix.length-1;
    const width = matrix[0].length-1;
    for (let i=height; i>=0; i--) {
        for (let j=width; j>=0; j--) {
            const right = j < width ? Number(matrix[i][j+1]) : 0;
            const diag = i < height && j < width ? Number(matrix[i+1][j+1]) : 0
            const bottom = i < height ? Number(matrix[i+1][j]) : 0;
            matrix[i][j] = matrix[i][j] === '0' ? 0 : 
                Math.min(right, diag, bottom) + 1;
            max = Math.max(max, matrix[i][j] * matrix[i][j]);
        }  
    }
    return max;
};
Maximal Square