Maximal Square

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 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.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Dynamic programming, dp[i][j] stores the maximum side length of square whose bottom-right coordinate is (i, j)

dp[i][0] = matrix[i][0] – ‘0’

dp[0][i] = matrix[0][i] – ‘0’

dp[i][j] = 0 if matrix[i][j] == 0

dp[i][j] = 1 + min(dp[i – 1][j], dp[i – 1][j – 1], dp[i][j – 1])

//dp stores the maximum side length of square whose bottom-right coordinate is (i, j)
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int ans = 0;
        if(matrix.size() == 0) return 0;
        int dp[matrix.size()][matrix[0].size()];
        for(int i = 0; i < matrix.size(); i++){
            if(matrix[i][0] == '0'){
                dp[i][0] = 0;
            }
            else{
                dp[i][0] = 1;
                ans = 1;
            }
        }
        for(int j = 0; j < matrix[0].size(); j++){
            if(matrix[0][j] == '0'){
                dp[0][j] = 0;
            }
            else{
                dp[0][j] = 1;
                ans = 1;
            }
        }
        for(int i = 1; i < matrix.size(); i++){
            for(int j = 1; j < matrix[0].size(); j++){
                if(matrix[i][j] == '0'){
                    dp[i][j] = 0;
                }
                else{
                    dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j]));
                }
                ans = max(ans, dp[i][j]);
            }
        }
        return ans * ans;
    }
    
};