0221. Maximal Square

https://leetcode.com/problems/maximal-square

Description

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.

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

Example 2:

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

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'.

ac1: DP

Typical DP that makes use of top/left/top-left.

class Solution {
    public int maximalSquare(char[][] matrix) {
        int max = 0;

        for (int r = 0; r < matrix.length; r++) {
            for (int c = 0; c < matrix[0].length; c++) {
                if (matrix[r][c] == '0') continue;
                if (r - 1 >= 0 && c - 1 >= 0) {
                    int min = Math.min(Math.min(matrix[r-1][c-1] - '0', matrix[r-1][c] - '0'), matrix[r][c-1] - '0');
                    matrix[r][c] = (char)('0' + min + 1);
                }

                max = Math.max(max, matrix[r][c] - '0');
            }
        }

        return max * max;
    }
}