# Maximal Square - Dynamic Programming / Grid

the default value for a int array is 0. so need for the else block. Also we can check for index i or j is 0 and simply assign it to 1 instead of looping 3 times.

``````public static int maximalSquare(char[][] matrix) {
int dp [][] = new int [matrix.length][matrix.length];
int max = 0;
for(int i=0; i<dp.length;i++){
for(int j=0;j<dp.length;j++){
if(matrix[i][j] == '1'){
if(i == 0 || j == 0){
dp[i][j] = 1;
}else {
dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
}
max = Math.max(max, dp[i][j]);
}

}
}
return max * max;
}
``````

Space optimized to O(cols):

``````    var rows = m.length + 1;
var cols = m.length + 1;
var max = 0;

var dp = new int[cols];
var prevTopLeft = 0;

for (int r = 1; r < rows; r++) {
for (int c = 1; c < cols; c++) {
var current = dp[c];
if (m[r - 1][c - 1] == '1') {
dp[c] = Math.min(Math.min(dp[c], dp[c - 1]), prevTopLeft) + 1;
max = Math.max(max, dp[c]);
}
else {
dp[c] = 0;
}
prevTopLeft = current;
}
}

return max * max;
``````

In the above diagram dp[r][c-1] = 2 and dp[r-1][c] =2
so the side length of bottom right cell dp[r][c] = min(2, 2, 1)+1 = 2

the bottom right above cell will be 2

Please correct me if I am wrong …I am bit confused with the above graphical explanation.

I agree. The graphical explanation got confusing after the 4th slide. Can you please clarify the explanation?

doesnt the code that says #fill top row actually fill the leftmost column? We are iterating through the rows and staying at column 0 in the code. Vice versa for the code thats for filling the leftmost column

Very complicated explanation… I’m still confused.

Any suggestion on this top down solution?

``````int dfs(int m, int n, vector<vector<int>> & matrix, vector<vector<int>> & memo, int & best) {
if(m < 0 || n < 0) return 0;

if(memo[m][n] != 0){
return memo[m][n];
}

int row = dfs(m-1, n, matrix, memo, best);
int col = dfs(m, n-1, matrix, memo, best);
int dia = dfs(m-1, n-1, matrix, memo, best);

if(matrix[m][n])
memo[m][n] = 1 + min(min(row, col), dia);

best = max(best, memo[m][n]);

return memo[m][n];
}
``````