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.

Analysis

DP problem: Can be optimized further to use only 1D matrix. See reference for more details.

• State: matrix[i][j]和用它左上部分所有elements能够达到的最大square size
• Initialize: 第一排和第一列dp[i][j]=matrix[i][j]
• Transfer: 如果matrix[i][j]==0, dp[i][j]=0; otherwise, dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
• Return: dp[i][j]的最大值

Code

public int maximalSquare(char[][] matrix) {
        int res = 0;
        if (matrix==null || matrix.length==0 || matrix[0].length==0) {return res;}
        int m = matrix.length;
        int n = matrix[0].length;

        int[][] dp = new int[m][n];

        for (int i=0; i<m; i++){
            for (int j=0; j<n; j++){
                if (i==0 || j==0){
                    dp[i][j]=matrix[i][j]=='0'?0:1;
                }
                else {
                    if (matrix[i][j]=='0'){dp[i][j]=0;}
                    else {dp[i][j]=Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1;}
                }
                res = Math.max(res, dp[i][j]);
            }
        }

        return res*res;
    }

Reference

Leetcode