Java DP Solution 17ms


  • 0
        private int maxSize = 0;
    
        private int min(int n1, int n2, int n3) {
            return n1 < n2 ? (n1 < n3 ? n1 : n3) : (n2 < n3 ? n2 : n3);    
        }
        
        /**
         * Dynamic Programming Solution
         * Reference: https://www.youtube.com/watch?v=_Lf1looyJMU
         */
        public int maximalSquare(char[][] matrix) {
            if(null == matrix){
                return -1;
            }
            
            int row = matrix.length;
            if(row < 1) {
                return 0;
            }
        
            int col = matrix[0].length;
            
            int result[][] = new int[row+1][col+1];
            for(int i=0; i<row; i++) {
                for(int j=0; j<col; j++) {
                    if(matrix[i][j] == '1') {
                        result[i+1][j+1] = min(result[i+1][j], result[i][j], result[i][j+1]) + 1;
                    
                        int size = result[i+1][j+1];
                        
                        if(size > maxSize) {
                            maxSize = size;
                        }
                    }
                }
            }
            
            return (int) Math.pow(maxSize, 2);
        }
    

Log in to reply
 

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