Maximal Square

1package pkg5leetcode.official75;2 3/*4 * Maximal Square | LC 2215 * APPROACH: DP side length of largest square ending at cell.6 * COMPLEXITY: Time O(mn), Space O(mn)7 */8public class official75_LC221MaximalSquare {9    static int maximalSquare(char[][] matrix) {10        int m = matrix.length, n = matrix[0].length;11        int[][] dp = new int[m + 1][n + 1];12        int best = 0;13        for (int i = 1; i <= m; i++)14            for (int j = 1; j <= n; j++)15                if (matrix[i - 1][j - 1] == '1') {16                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));17                    best = Math.max(best, dp[i][j]);18                }19        return best * best;20    }21 22    public static void main(String[] args) {23        check(maximalSquare(new char[][]{{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}}) == 4, "case1");24        check(maximalSquare(new char[][]{{'0','1'},{'1','0'}}) == 1, "case2");25        System.out.println("all tests passed");26    }27 28    static void check(boolean cond, String name) {29        if (!cond) throw new AssertionError("FAILED: " + name);30        System.out.println("  PASS " + name);31    }32}