Java 12ms 30 lines O(m*n) solution


  • 0

    This problem is tagged as dynamic programming. The question is how to use dp.
    I use a matrix called maxsqr to memorize the length of a square whose bottom right corner is at [i] [j].
    For the cells at the top or at the left border of the entire matrix, since there are no cell sitting at their left hand side or top. Once matrix[i][j] == '1', maxsqr[i][j] = 1 (i==0 or j==0).
    For the rest cells, if matrix[i][j] is 1, the cells on its top, left and top-left need to be checked. Those cells record the max number of contiguous '1's can be reached by the current cell's neighbor.
    The minimum of those 3 cells + 1 is the value of the current cell (maxsqr[i][j]).
    Keep refreshing maxedge using maxsqr[i][j] to track the longest edge of the square and done!.

    public int maximalSquare(char[][] matrix) {
        int maxedge = 0;//max length of the edge of one square
        int m = matrix.length;
        if(m==0) return 0;
        int n = matrix[0].length;
        if(n==0) return 0;
        int[][] maxsqr = new int[m][n];
        //initialize cells on top and left. 
        //top
        for(int i = 0;i<m;i++){
            if(matrix[i][0]=='1'){
                maxsqr[i][0] = 1;
                maxedge = maxedge>maxsqr[i][0]?maxedge:maxsqr[i][0];
            }
        }
        //lhs
        for(int j = 0;j<n;j++){
            if(matrix[0][j]=='1'){
                maxsqr[0][j] = 1;
                maxedge = maxedge>maxsqr[0][j]?maxedge:maxsqr[0][j];
            }
        }
        if(m>1&&n>1){
            for(int i = 1;i<m;i++){
                for(int j = 1;j<n;j++){
                    if(matrix[i][j]=='1'){
                        int mineighbor = Math.min(Math.min(maxsqr[i-1][j-1],maxsqr[i][j-1]),maxsqr[i-1][j]);
                        maxsqr[i][j] = mineighbor + 1;
                        maxedge = maxedge>maxsqr[i][j]?maxedge:maxsqr[i][j];
                    }
                }
            }
        }
        return maxedge*maxedge;
    }

Log in to reply
 

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