221. Maximal Square (Medium)

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.

Solution: DP

Well, this problem desires for the use of dynamic programming. They key to any DP problem is to come up with the state equation. In this problem, we define the state to be the maximal size of the square that can be achieved at point (i, j), denoted as P[i][j]. Remember that we use size instead of square as the state (square = size^2).

In fact, P[i][j] = min(P[i - 1][j], P[i][j - 1], P[i - 1][j - 1]) + 1 in this case.

Taking all these together, we have the following state equations.

1. P[0][j] = matrix[0][j] (topmost row);
2. P[i][0] = matrix[i][0] (leftmost column);
3. For i > 0 and j > 0: if matrix[i][j] = 0, P[i][j] = 0; if matrix[i][j] = 1, P[i][j] = min(P[i - 1][j], P[i][j - 1], P[i - 1][j - 1]) + 1.

version 1: 6ms

Space Complexity: $$O(mn)$$

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

version 2: 6ms

Space Complexity: $$O(n)$$

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int m = matrix.size(), n = matrix[0].size();
        vector<int> dp(n+1,0);
        int res = 0, pre = 0;

        for (int i = 0; i < m; ++i) {
            pre = 0;
            for (int j = 1; j <= n; ++j) {
                int tmp = dp[j];
                if (matrix[i][j-1] == '1') {
                    dp[j] = min(pre, min(dp[j], dp[j-1]))+1;
                    res = max(res, dp[j]);
                } else dp[j] = 0;
                pre = tmp;
            }
        }
        cout << res;
        return res*res;
    }
};