Given an m x n binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.
Test Cases
Example 1:
| 1 | 0 | 1 | 0 | 0 |
| 10 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 0 | |
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4
Example 2:
| 0 | 1 |
| 1 | 0 |
Input: matrix = [["0","1"],["1","0"]]
Output: 1
Solution
class Solution {
public int maximalSquare(char[][] matrix) {
int n = matrix.length, m = matrix[0].length;
int[][] dp = new int[n+1][m+1];
int max = 0;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if (matrix[i-1][j-1] == '1') {
dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
max = Math.max(max, dp[i][j]);
}
}
}
return max*max;
}
}