2 Java Solutions, both DP, 308ms and 348ms


  • 0
    W

    solution 1: 308ms,

    public class Solution {
        public int maximalSquare(char[][] matrix) {
            int m = matrix.length;
            if(m==0) return 0;
            int n = matrix[0].length;
            int[][] A = new int[m][n];
            int sqr = 0;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(matrix[i][j]=='0') A[i][j]=0;
                    else A[i][j]=i==0||j==0?1:Math.min(Math.min(A[i-1][j],A[i][j-1]),A[i-1][j-1])+1;
                    sqr = Math.max(sqr,A[i][j]*A[i][j]);
                }
            }
            return sqr;
        }    
    }
    

    solution 2: 348ms

    public class Solution {
            public int maximalSquare(char[][] matrix) {
                int m = matrix.length;
                if(m==0) return 0;
                int n = matrix[0].length;
                int[][] height = new int[m][n];
                for(int i=0; i<m; i++){
                    for(int j=0; j<n; j++){
                        if(matrix[i][j]=='0') height[i][j]=0;
                        else height[i][j]=i==0? 1:height[i-1][j]+1;
                    }
                }
                int max = 0;
                for(int i=0;i<m;i++){
                    max = Math.max(max,maxSquare(height[i]));
                }
                return max;
            }
            private int maxSquare(int[] height){
                int i=0, j=0, min=height[0], sqr=0, len=0;
                while(j<height.length&&i<=j){
                    min = height[i];
                    for(int k=i+1;k<j+1;k++){
                        min = Math.min(min,height[k]);
                    }
                    len = Math.min(min,j-i+1);
                    sqr = Math.max(sqr,len*len);
                    if(min<j-i+1){
                        i=j-min+1;
                    }
                    j++;
                }
                return sqr;
            }
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.