Q1 Maximal Square - LeetCode 221
Wed Mar 01 2023 13:59:11 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
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
}
}
content_copyCOPY
https://leetcode.com/problems/maximal-square/editorial/
Comments