221. Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

Thoughts:

1. different approach from maximal rectangle problems (84 and 85 )since it is a square (current state value only depends on top, left and top-left corner

2. f[i][j] number of maximal square from matrix[0, ...i -1][0,...j-1] so far

3. initial state: f[i][0] = f[0][j] = 0

4. recursive state : f[i][j] = min(f[i-1][j], f[i][j-1], f[i-1][j-1]) for (1<= i <= matrix.size(); 1<=j<=matrix[0].size()).

5. further optimization

Code Time Complexity O(row * col), Space Complexity O(row * col)

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

        return ans * ans;
    }
};

Code (Optimization): with Space Complexity O(row) or O(col)

int maximalSquare(vector<vector<char>>& matrix) {
    if (matrix.empty()) return 0;
    int m = matrix.size(), n = matrix[0].size();
    vector<int> dp(m + 1, 0); // 0 padding on the top
    int maxsize = 0, pre = 0;
    for (int j = 0; j < n; j++) {
        for (int i = 1; i <= m; i++) {
            int temp = dp[i]; 
            if (matrix[i - 1][j] == '1') {
                dp[i] = min(dp[i], min(dp[i - 1], pre)) + 1; //dp[i]: dp[i][j-1], dp[i-1]: dp[i-1][j]
                maxsize = max(maxsize, dp[i]);
            }
            else dp[i] = 0; 
            pre = temp; // serve as dp[i-1][j-1] for the next iteration 
        }
    }
    return maxsize * maxsize;
}

Special Thanks to jianchao.li.fighter's solution