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.

Input: 

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

Output: 4

Solution 1:

Use histogram method:

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) return 0;
        int n = matrix[0].length;
        if (n == 0) return 0;
        int[][] M = new int[m][n + 1];
        for (int j = 0; j < n; j ++) {
            M[0][j] = matrix[0][j] - '0';
        }
        M[0][n] = -1;
        for (int i = 1; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                M[i][j] = matrix[i][j] == '0' ? 0 : M[i - 1][j] + 1;
            }
            M[i][n] = -1;
        }
        int max = 0;
        for (int i = 0; i < m; i ++) {
            // 3 1 3 2 2 (0)
            
            int[] arr = M[i];
            Deque<Integer> stack = new ArrayDeque<>();
            for (int j = 0; j <= n; j ++) {
                int curr = arr[j];
                while (!stack.isEmpty() && curr < arr[stack.peekFirst()]) {
                    int height = arr[stack.pop()];
                    int left = stack.isEmpty() ? 0 : stack.peekFirst() + 1;
                    int width = j - left;
                    int edge = Math.min(height, width);
                    max = Math.max(max, edge * edge);
                }
                stack.push(j);
            }
        }
        return max;
    }
}

dp

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