Maximal Square

ID:221

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.

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

Idea

Dynamic Programming

If a cell is surrounded by 1s, this cell can form a new square with 1 more length ([i-1][j], [i][j-1][i-1][j-1] all 1, [i][j] can form a 2x2 square)

Extensively, if ([i-1][j], [i][j-1][i-1][j-1] all already in a 2x2 square, [i][j] can form a 3x3 square)

So, heuristic: dp[i][j] = Min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

Code

public int maximalSquare(char[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int[][] dp = new int[rows + 1][cols + 1];
        int maxsqlen = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (matrix[i-1][j-1] == '1'){
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                    maxsqlen = Math.max(maxsqlen, dp[i][j]);
                }
            }
        }
        return maxsqlen * maxsqlen;
    }