Leetcode
Dynamic Programming
221 Maximal Square

1. Question

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
For example, given the following matrix:
1
1 0 1 0 0
2
1 0 1 1 1
3
1 1 1 1 1
4
1 0 0 1 0
Copied!
Return 4.

2. Implementation

(1) DP
1
class Solution {
2
public int maximalSquare(char[][] matrix) {
3
if (matrix == null || matrix.length == 0) {
4
return 0;
5
}
6
7
int m = matrix.length, n = matrix[0].length;
8
// dp[i][j] means the edge of square which is at bottom right at (i, j)
9
int[][] dp = new int[m][n];
10
int maxSize = 0;
11
12
for (int i = 0; i < m; i++) {
13
for (int j = 0; j < n; j++) {
14
if (i == 0 || j == 0) {
15
dp[i][j] = matrix[i][j] - '0';
16
}
17
else if (matrix[i][j] == '1') {
18
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
19
}
20
else {
21
dp[i][j] = 0;
22
}
23
24
maxSize = Math.max(maxSize, dp[i][j]);
25
}
26
}
27
return maxSize * maxSize;
28
}
29
}
Copied!

3. Time & Space Complexity

DP: 时间复杂度O(mn), 空间复杂度O(mn)