Comment on page
maximal-square
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4
This is dynamic programming, which can solve it by breaking down into smaller subproblems. DP problem, the hard part is to come up with formular function, first we init dp:
- m, represents rows of the matrix
- n, represents columns of the matrix
dp[m+1][n+1]
dp formular function:
for each
matrix[i-1][j-1]='1', update max, max=max(max, dp[i][j]After iterate matrix, we get the maximum edge of square,
return max * max;For example:
Maximal Square
Time Complexity:
O(N*M)Space Complexity:
O(N*M)- N - the number of rows of matrix
- M - the number of columns of matrix
class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
int max = 0;
int row = matrix.length;
int col = matrix[0].length;
int[][] dp = new int[row + 1][col + 1];
for (int r = 1; r <= row; r++) {
for (int c = 1; c <= col; c++) {
if (matrix[r - 1][c - 1] == '1') {
dp[r][c] = Math.min(dp[r][c - 1], Math.min(dp[r - 1][c], dp[r - 1][c - 1])) + 1;
max = Math.max(max, dp[r][c]);
}
}
}
return max * max;
}
}
Last modified 3yr ago