Skip to content

Instantly share code, notes, and snippets.

@rohandalvi
Last active December 4, 2019 07:06
Show Gist options
  • Save rohandalvi/c82a5bda8e99907ed37cb4ac531a004b to your computer and use it in GitHub Desktop.
Save rohandalvi/c82a5bda8e99907ed37cb4ac531a004b to your computer and use it in GitHub Desktop.
class Solution {
public int maximalSquare(char[][] matrix) {
if(matrix.length == 0) return 0;
int[][] dp = new int[matrix.length][matrix[0].length];
Integer max = 0;
for(int i = 0;i<dp.length;i++) {
//initialize
if(matrix[i][0]=='1') {
max = 1;
dp[i][0] = 1;
}
}
for(int j = 0;j<dp[0].length;j++) {
if(matrix[0][j]=='1') {
max = 1;
dp[0][j]=1;
}
}
for(int i = 1;i<dp.length;i++) {
for(int j = 1;j<dp[i].length;j++) {
if(matrix[i][j]=='1'){
dp[i][j] = 1+Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
max = Math.max(max, dp[i][j]);
}
}
}
return max*max;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment