221. Maximal Square - cocoder39/coco39_LC GitHub Wiki

221. Maximal Square

consider dp when facing "maximal" problem. Compare this problem with [link to largest rectangle, container..]

dp[i][j] is the max side length of thr square whose bottom right vertex is matrix[i][j], then dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;

2D-DP template: initialize first row and col, then traversal the rest bins

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, vector<int>(n));
        int len = 0;
        
        for (int i = 0; i < m; i++) { 
            dp[i][0] = matrix[i][0] == '1';
            len = max(len, dp[i][0]);
        }
        for (int j = 0; j < n; j++) { 
            dp[0][j] = matrix[0][j] == '1';
            len = max(len, dp[0][j]);
        }
            
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '1') {    
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                    len = max(len, dp[i][j]);
                }
            }
        }
        return len * len;
    }

updating dp[cur][j] without considering matrix[cur][j] == '0', generating bug

int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].size();
        vector<vector<int>> dp(2, vector<int>(n));
        int len = 0;

        for (int j = 0; j < n; j++) { 
            dp[0][j] = matrix[0][j] == '1';
            len = max(len, dp[0][j]);
        }

        int pre = 0, cur = 1;
        for (int i = 1; i < m; i++) {
            dp[pre][0] = matrix[i - 1][0] == '1';
            dp[cur][0] = matrix[i][0] == '1';
            for (int j = 1; j < n; j++) {
                dp[cur][j] = matrix[i][j] == '1' ? min(dp[cur][j - 1], min(dp[pre][j], dp[pre][j - 1])) + 1 : 0;  
                len = max(len, dp[cur][j]);
            }
            swap(pre, cur);
        }
        return len * len;
    }
⚠️ **GitHub.com Fallback** ⚠️