221. Maximal Square

Given an m x n binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

1
2
3
4
Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

1
2
3
4
Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

1
2
3
4
Example 3:

Input: matrix = [["0"]]
Output: 0

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] is ‘0’ or ‘1’.

Solution

 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
class Solution {
    public int maximalSquare(char[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] dp = new int[n][m];
        int max = 0;
        for (int j = 0; j < m; j++) {
            dp[0][j] = matrix[0][j] == '0' ? 0 : 1;
            max = Math.max(dp[0][j], max);
        }
        
        for (int i = 0; i < n; i++) {
            dp[i][0] = matrix[i][0] == '0' ? 0: 1;
            max = Math.max(dp[i][0], max);
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (matrix[i][j] == '0') {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1;
                }
                max = Math.max(dp[i][j], max);
            }
        }   
        return max * max;
    }
    
    int min(int a, int b, int c) {
        return Math.min(a, Math.min(b,c));
    }
}

Solution#

Solution