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.

Example:

Input: 

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

Output: 4

// 2D array DP
int maximalSquare(vector<vector<char>>& matrix) { // time: O(m * n); space: O(m * n)
    if (matrix.empty() || matrix[0].empty()) return 0;
    int m = matrix.size(), n = matrix[0].size();
    int max_size = 0;
    vector<vector<int> > dp(m, vector<int>(n, 0));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == 0 || j == 0 || matrix[i][j] == '0')
                dp[i][j] = matrix[i][j] - '0';
            else 
                dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
            max_size = max(max_size, dp[i][j]);
        }
    }
    return max_size * max_size;
}

// 1D array DP
int maximalSquare(vector<vector<char>>& matrix) { // time: O(m * n); space: O(n)
    if (matrix.empty() || matrix[0].empty()) return 0;
    int m = matrix.size(), n = matrix[0].size();
    int max_size = 0;
    vector<int> dp(n, 0);
    int upper_left = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int upper = dp[j];
            if (i == 0 || j == 0 || matrix[i][j] == '0') {
                dp[j] = matrix[i][j] - '0';
            } else {
                dp[j] = min({upper_left, dp[j - 1], dp[j]}) + 1;
            }
            max_size = max(max_size, dp[j]);
            upper_left = upper;
        }
    }
    return max_size * max_size;
}