# Clear C++ solution, no extra space, 12 ms.

• A square with '1' means any '0' will interrupt counting of it's right/down/right-down, and '1' will 'inherit' the existing counting result.

Sine the target is a square, we shall take the smallest counting result from up/left/up-left.

So for each element '0', it doesn't inherit previous accumulated counting;

And for each element '1', it takes the smallest number from left/up/left-up and add 1 to it

``````int maximalSquare(vector<vector<char>>& matrix) {
int rst = 0;
for(int ii=0; ii<matrix.size(); ++ii)
{
for(int jj=0; jj<matrix[0].size(); ++jj)
{
int a = (ii&&jj) ? matrix[ii-1][jj-1] : 0;
int b = (ii) ? matrix[ii-1][jj] : 0;
int c = (jj) ? matrix[ii][jj-1] : 0;

matrix[ii][jj] = (matrix[ii][jj]>'0') ? (min(a, min(b, c))+1) : 0;

rst = max(rst, matrix[ii][jj]*matrix[ii][jj]);
}
}
return rst;
}``````

• How would you store value>9 (possible) in a char matrix?

• The algorithm still use space by changing the input matrix.

And as comment below by san-ag pointed out, this algorithm does not work when the value over 127.

• Why does it work? I mean a,b,c all maybe 48 or 49, then the minimal of them plus 1 becomes 49 or 50. Then the square of it can never be 4 for example... I don't understand...

• easy dp, O(MN) time and space no optimization with space

``````class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size();
if(m==0)
return 0;
int n = matrix[0].size();

vector<vector<int>> dp(m+1,vector<int>(n+1,0));
int max_len = 0;
for(int i=1;i<m+1;i++)
{
for(int j=1;j<n+1;j++)
{
if(matrix[i-1][j-1] == '0')
dp[i][j] = 0;
else
{
dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1])) + 1;
}

max_len = max(max_len,dp[i][j]);
}

}
return max_len*max_len;

}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.