class Solution { public int max = 0; public int maximalSquare(char[][] matrix) { //Q-1 of dp level 2 , every cell denotes maxmimum submatrix square they can make //dividing the matrix in 4 parts and solving them indivisually int m = matrix.length , n = matrix[0].length; int dp[][] = new int[m][n]; //max subsquare last row can make will be 1 if there is a 1 present in matrix cell for(int j = 0 ; j < n ; j++){ dp[m-1][j] = matrix[m-1][j] -'0' ; max = Math.max(max , dp[m-1][j]); } //max subsquare last col can make will be 1 if there is a 1 present in matrix cell for(int i = 0 ; i < m; i++){ dp[i][n-1] = matrix[i][n-1] -'0' ; max = Math.max(max , dp[i][n-1]); } //rest of the matrix for(int i = m-2 ; i >= 0 ; i--){ for(int j = n-2 ; j >= 0 ; j--){ if(matrix[i][j] == '1'){ //minimum of next , below and diagnolly below cell + 1 dp[i][j] = Math.min(dp[i][j+1], Math.min(dp[i+1][j+1],dp[i+1][j])) +1; max = Math.max(max , dp[i][j]); } } } return max*max; //we have to return area } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter