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


  • 22
    D

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

  • 0
    S

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


  • 0
    P

    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.


  • 0
    L

    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...


  • 0
    S

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

Log in to reply
 

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