Description

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

Solution

DP, time O(mn), space O(mn)

dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1.

class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m + 1][n + 1];
        int maxSquare = 0;
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '0') {
                    continue;
                }
                
                dp[i + 1][j + 1] 
                    = 1 + Math.min(Math.min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]);
                maxSquare = Math.max(dp[i + 1][j + 1] * dp[i + 1][j + 1], maxSquare);
            }
        }
        
        return maxSquare;
    }
}

DP, time O(mn), space O(n)

image.png

从上面的解法可以看出，对于dp数组，第i + 1行只依赖与第 i 行。所以我们可以将二维dp降成一维dp。

class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        int[] dp = new int[n + 1];
        int maxLen = 0;
        
        for (int i = 0; i < m; ++i) {
            int pre = 0;
            
            for (int j = 0; j < n; ++j) {
                int tmp = dp[j + 1];
                
                if (matrix[i][j] == '0') {
                    dp[j + 1] = 0;  // important
                } else {
                    dp[j + 1] = 1 + Math.min(Math.min(dp[j], pre), dp[j + 1]);
                    maxLen = Math.max(dp[j + 1], maxLen);
                }
               
                pre = tmp;
            }
        }
        
        return maxLen * maxLen;
    }
}