DP-7. Maximal Square

Problem

LeetCode 221. 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

Explanation

This is an optimal problem, so we can natrually think of DP. This is less tricky compared to Maximal Rectangle. As this is a square, we can find the maximum side length. So, every time, we only have to check the adjacent four sides. We can initialize a 2D array of the same shape, dp. Every value in the dp means the maximum side length based on this point.

If this is ‘0’, we know every square contains this point is 0. We can keep 0. If this is ‘1’, we compare the left point, the upper point and the left and upper point, get the minimum point and plus 1. What does that mean? Take an example, if the three points are all 1, then the point should be 2, which means, the maximum square created by these 4 points is 2 * 2. If the three points are 1, 1, 2, and the point can only be 1 + 1 = 2, which means, the maximum square created by these 4 points is 2 * 2. We should also use a max variable to save the maximum side length. Finally, remember to return the square other then the side length.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;

int m = matrix.length, n = matrix[0].length;

int[][] dp = new int[m + 1][n + 1];
int max = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '0') {
dp[i + 1][j + 1] = 0;
} else {
dp[i + 1][j + 1] = Math.min(Math.min(dp[i + 1][j], dp[i][j + 1]), dp[i][j]) + 1;
max = Math.max(max, dp[i + 1][j + 1]);
}
}
}

return max * max;
}
}