Java 11ms O(n^3) Simple Solution, 41 lines


  • 0

    Brutal Force:
    Idea: For each position which is '1', find the maximum possible square starts from this position. O(n^3) in the worst case.

    public class Solution {
        public int maximalSquare(char[][] matrix) {
            int maxLen = 0;
            int m = matrix.length;
            int n = 0;
            if( m > 0 ){
                n = matrix[0].length;
            }
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    if(matrix[i][j] == '1'){
                        int tmpLen = 1;
                        int oldLen;
                        do{
                            oldLen = tmpLen;
                            if(i + tmpLen < m &&
                               j + tmpLen < n &&
                               findSquare(matrix,tmpLen+1,i,j)){
                                tmpLen++;
                            }
                        }while(oldLen != tmpLen);
                        if(oldLen > maxLen) maxLen = oldLen;
                    }
                }
            }
            return maxLen * maxLen;
        }
        public boolean findSquare(char[][] map, int length, int x, int y){
            for(int i = x; i < x+length; i++){
                if(map[i][y+length-1] == '0'){
                    return false;
                }
            }
            for(int j = y; j < y+length; j++){
                if(map[ x + length - 1][j] == '0'){
                    return false;
                }
            }
            return true;
        }
    }
    

Log in to reply
 

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