Detailed explanation with easy Java code, beats 80%. O(m*n) time and space


  • 0
    Y
    public class Solution {
        public static int maximalSquare(char[][] matrix) {
            //Main idea: dynamic programming
            //base case: M[i][j] = matrix[i][j]  if i==0 || j==0
            //subproblem: M[i][j] = min(M[i-1][j],M[i][j-1],M[i-1][j-1])+1  if matrix[i][j]==1
            //                    = 0    if matrix[i][j] = 0
            //at the same time, update max when larger than max
            
            //corner case
            if(matrix == null || matrix.length == 0) {
                return 0;
            }
            
            int max = 0;
            int row = matrix.length;
            int col = matrix[0].length;
            int[][] M = new int[row][col];
            
            //base case1: first row
            for(int j = 0; j < col; j++) {
                M[0][j] = matrix[0][j]-'0';
                if(M[0][j] == 1) {
                    max = 1;
                }
            }
            //base case2: first col
            for(int i = 1; i < row; i++) {
                M[i][0] = matrix[i][0]-'0';
                if(M[i][0] == 1) {
                    max = 1;
                }
            }
            
            
            //induction rule
            for (int i = 1; i < row; i++) {
                for (int j = 1; j < col; j++) {
                    if(matrix[i][j]-'0' == 0) {
                        M[i][j] = 0;
                    }
                    else{
                        M[i][j] = Math.min(M[i-1][j], M[i][j-1]);
                        M[i][j] = Math.min(M[i][j], M[i-1][j-1]);
                        M[i][j]++;
                        //update max when necessary
                        max = Math.max(max,M[i][j]);
                    }
                }
            }
            return max*max;
        }
    }
    

Log in to reply
 

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