0%

Leetcode221-maximalSquare

Description

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

1
2
3
4
5
6
7
8
Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

Solution

Method 1

dp[i][j] represents the length of the square which lower right corner is located at (i, j).

If the value of this cell is also 1, then the length of the square is the minimum of: the one above, its left, and diagonal up-left value +1. Because if one side is short or missing, it will not form a square.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m + 1][n + 1];
int res = 0;
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(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
res = Math.max(res, dp[i][j] * dp[i][j]);
}
}
}
return res;
}
}

Method 2: More general, using Rectangle method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;
int m = matrix.length;
int n = matrix[0].length;
int[] left = new int[n];
int[] right = new int[n];
int[] height = new int[n];
Arrays.fill(left, 0);
Arrays.fill(right, n - 1);
Arrays.fill(height, 0);
int res = 0;
for (int i = 0; i < m; i++){
int curLeft = 0;
int curRight = n - 1;
for(int j = 0; j < n; j++){
if (matrix[i][j] == '1'){
height[j]++;
left[j] = Math.max(left[j], curLeft);
}
else{
height[j] = 0;
left[j] = 0;
curLeft = j + 1;
}
}
for (int j = n - 1; j >= 0; j--){
if (matrix[i][j] == '1'){
right[j] = Math.min(right[j], curRight);
}
else{
right[j] = n - 1;
curRight = j - 1;
}
int len = Math.min(height[j], right[j] - left[j] + 1);
res = Math.max(res, len * len);
}
}
return res;
}
}