Maximal Square - Dynamic Programming / Grid

Problems
1

https://algo.monster/problems/maximal_square

2

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[0].length];
    int max = 0;
    for(int i=0; i<dp.length;i++){
        for(int j=0;j<dp[0].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;
}
3

Space optimized to O(cols):

    var rows = m.length + 1;
    var cols = m[0].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;
4

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.

5

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

6

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

7

Very complicated explanation… I’m still confused.

8

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];
}