Given a binary matrix filled with 0s and 1s, find the largest square containing only 1s and return its area.
Input: [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] → Output: 4Input: [["0","1"],["1","0"]] → Output: 1
dp[i][j] = side length of largest square with bottom-right corner at (i,j). If matrix[i][j]==1: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.
- dp[i][j] = 0 if matrix[i][j] == 0.
- Otherwise: dp[i][j] = min(left, top, top-left diagonal) + 1.
- Track maxSide = max(dp[i][j]).
- Return maxSide * maxSide.
class Solution {
public int maximalSquare(char[][] matrix) {
int m = matrix.length, n = matrix[0].length, maxSide = 0;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i-1][j-1] == '1') {
dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
}
- Time Complexity: O(M*N)
- Space Complexity: O(M*N)