Maximal Square

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 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

Return 4.
Solution:
1. public class Solution {
2. public int maximalSquare(char[][] a) {
3. if (a == null || a.length == 0 || a[0].length == 0)
4. return 0;
5. 6. int max = 0;
7. int n = a.length;
8. int m = a[0].length;
9. 10. // recurrence formula:
11. // dp(i, j) = min{ dp(i-1, j-1), dp(i-1, j), dp(i, j-1) }
12. int[][] dp = new int[n + 1][m + 1];
13. 14. for (int i = 1; i <= n; i++) {
15. for (int j = 1; j <= m; j++) {
16. if (a[i - 1][j - 1] == '1') {
17. dp[i][j] = Math.min(
18. dp[i - 1][j - 1],
19. Math.min(dp[i - 1][j], dp[i][j - 1])
20. ) + 1;
21. max = Math.max(max, dp[i][j]);
22. }
23. }
24. }
25. 26. // return the area
27. return max * max;
28. }
29. }