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.

For example, given the following matrix:

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

Return 4.


This is actually a DP problem. For any point, to form a larger square, it's left, upper left, upper point should also be part of the square, so maximal length is the minimum of the three, if current point is 1. If current point is 0, it can not form any square.

public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] len = new int[m][n];
        int maxLen = 0;
        for (int i = 0; i < m; i++) {
            len[i][0] = matrix[i][0] - '0';
            maxLen = Math.max(maxLen, len[i][0]);
        }
            
        
        for (int j = 0; j < n; j++) {
            len[0][j] = matrix[0][j] - '0';
            maxLen = Math.max(maxLen, len[0][j]);
        }
            
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                len[i][j] = matrix[i][j] == '1' ? Math.min(len[i][j - 1], Math.min(len[i - 1][j - 1], len[i - 1][j])) + 1
                : 0;
                maxLen = Math.max(maxLen, len[i][j]);
            }
        }
        return maxLen * maxLen;
    }