DP #9 Largest square formed in a matrix

Maximal Square

Problem Statement: here

Solution:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0 (credits : Leetcode)

We want to count the number of one's in the maximum square sub matrix of given matrix. We can treat the index [i][j] as the ending point of our square and look at the maximumm square submatrix I can create. Let us call dp[i][j] the maximum size submatrix when [i,j] is the end point. 

We can compute dp[i][j] as: dp[i][j] = min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1]) + 1;

What's that and how does it come?? So, we want to create a square matrix with [i,j] as the ending index, dp[i-1][j] denotes the maximum sub-matrix size ending at [i-1,j]. Similarly for other two. For my current index, let us say x is the answer. That means, I can construct a square of side x which ends at [i,j]. For a square of side x, we must have it's length size, width size and diagnol size as well exactly equal to x. When we take min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1]) we are actually asking for the maximum side I can take and add 1 to it. Inclusion of dp[i-1][j] gives the horizontal side of square, dp[i][j-1] gives the vertical side of square and dp[i-1][j-1] gives the diagonal of square. When taken min of this 3, we get the side for our current possible square.

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int n = matrix.size();
        if (n == 0) return 0;
        int m = matrix[0].size();
        int dp[n][m];
        for(int i=0;i<n;i++) dp[i][0] = matrix[i][0]-'0';
        for(int j=0;j<m;j++) dp[0][j] = matrix[0][j]-'0';
        int mx = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if (i==0 || j==0){
                    mx = max(mx,dp[i][j]);
                    continue;
                }
                if (matrix[i][j] == '0'){
                    dp[i][j]  = 0;
                }
                else{
                    dp[i][j] = min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+1;
                    mx = max(mx,dp[i][j]);
                }
            }
        }
        return mx*mx;
    }
};